Premium
Average distance and maximum induced forest
Author(s) -
Hansen Pierre,
Hertz Alain,
Kilani Rim,
Marcotte Odile,
Schindl David
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20344
Subject(s) - mathematics , combinatorics , graph , conjecture , bipartite graph , bound graph , path graph , order (exchange) , discrete mathematics , graph power , line graph , finance , economics
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 strengthening 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). © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 31–54, 2009