Back

G-2007-07

Average Distance and Maximum Induced Forest

, , , , and

BibTeX reference

With the help of the Graffiti system, Fajtlowicz conjectured around 1992 that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced bipartite subgraph of G, denoted α2(G). We prove a strenghtening of this conjecture by showing that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced forest, denoted F(G). Moreover, we characterize the graphs maximizing the average distance among all graphs G having a fixed number of vertices and a fixed value of F(G) or α2(G). Finally, we conjecture that the average distance between two vertices of a connected graph is at most half the maximum order of an induced linear forest (where a linear forest is a union of paths).

, 26 pages

This cahier was revised in May 2008

Research Axis

Research applications

Publication

Average distance and maximum induced forest
, , , , and
Journal of Graph Theory, 60(1), 31–54, 2009 BibTeX reference