×

Average distance and maximum induced forest. (English) Zbl 1182.05049

Let \(G=(V,E)\) be a (connected) graph. The distance \(d(u,v)\) between two vertices \(u\) and \(v\) in \(G\) is the length (number of edges) of a shortest path between \(u\) and \(v\). The average distance \(\mu(G)\) of \(G\) is \(\frac{2}{n(n-1)}\sum\{d(u,v)\mid u,v\in V,\, u\not=v\}\) and \(F(G)\) is the maximum number of vertices that induce a forest in \(G\). The authors prove that \(\mu(G)\leq\frac{1}{2} F(G)\) for all connected graphs \(G\). This implies that \(\mu(G)\) is at most the maximum number of pairwise non-adjacent vertices in \(G\), proved in [F.R.K. Chung, ”The average distance and the independence number,” J. Graph Theory 12, No.2, 229–235 (1988; Zbl 0644.05029)]; see also [P. Dankelmann, ”Average distance and independence number”, Discrete Appl. Math. 51, No.1-2, 75–83 (1994; Zbl 0803.05020)]. The authors conjecture that \(\mu(G)\leq\frac{1}{2} C(G)\) for all connected graphs \(G\), where \(C(G)\) denotes the maximum number of vertices that induce a linear forest (a union of paths) in \(G\).

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Fajtlowicz, Written on the Wall, Electronic file of conjectures of Graffiti, 1986 (and updates), available at http://www.math.uh.edu/siemion.
[2] Chung, The average distance and the independence number, J Graph Theory 12 pp 229– (1988) · Zbl 0644.05029
[3] Dankelmann, Average distance and independence number, Discrete Appl Math 51 pp 75– (1994) · Zbl 0803.05020
[4] Berge, Graphs and Hypergraphs (1976)
[5] Caporossi, Variable neighborhood search for extremal graphs I. The AutoGraphiX system, Discrete Math 214 pp 29– (2000) · Zbl 0947.90130
[6] Plesnik, On the sum of all distances in a graph or digraph, J Graph Theory 8 pp 1– (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.