Bounds on distances for spanning trees of graphs.
Loading...
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In graph theory, there are several techniques known in literature for constructing
spanning trees. Some of these techniques yield spanning trees with many leaves. We
will use these constructed spanning trees to bound several distance parameters.
The cardinality of the vertex set of graph G is called the order, n(G) or n. The
cardinality of the edge set of graph G is called the size, m(G) or m. The minimum
degree of G, (G) or , is the minimum degree among the degrees of the vertices of
G: A spanning tree T of a graph G is a subgraph that is a tree which includes all
the vertices of G. The distance d(u; v) between two vertices u and v is the length
of a shortest u-v path of G. The eccentricity, ec (v), of a vertex v 2 V (G) is the
maximum distance from it to any other vertex in G. The diameter, diam(G) or d,
is the maximum eccentricity amongst all vertices of G. The radius, rad(G), is the
minimum eccentricity among all vertices of G. The average distance of a graph G,
(G), is the expected distance between a randomly chosen pair of distinct vertices.
We investigate how each constructed spanning tree can be used to bound diam-
eter, radius or average distance in terms of order, size and minimum degree. The
techniques to be considered include the radius-preserving spanning trees by Erd}os et
al, the Ding et al technique, and the Dankelmann and Entringer technique. Finally,
we use the Kleitman and West dead leaves technique to construct spanning trees
with many leaves for various values of the minimum degree k (for k = 3; 4 and
k > 4) and order n. We then use the leaf number to bound diameter.
Description
Master of Science in Applied Mathematics, University of KwaZulu-Natal, Westville, 2018.