### G-2007-07

# Average Distance and Maximum Induced Forest

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

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).

Published **January 2007**
,
26 pages

This cahier was revised in **May 2008**