Retour

# Average Distance and Maximum Induced Forest

## Pierre Hansen, Alain Hertz, Rim Kilani, Odile Marcotte et David Schindl

référence BibTeX

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

Ce cahier a été révisé en mai 2008

### Publication

Average distance and maximum induced forest
, , , et
Journal of Graph Theory, 60(1), 31–54, 2009 référence BibTeX