A Characterization of Graphs Where the Independence Number Equals the Radius

作者：DeLaVina Ermelinda; Larson Craig E^*; Pepper Ryan; Waller Bill

来源：Graphs and Combinatorics, 2012, 28(3): 315-332.

DOI：10.1007/s00373-011-1054-x

• Ciliate
• Bipartite number
• Forest number
• Independence number
• Path number
• Radius
• Scaffold
• Tree number

In a classical 1986 paper by Erdos, Saks and Sas every graph of radius r has an induced path of order at least 2r - 1. This result implies that the independence number of such graphs is at least r. In this paper, we use a result of S. Fajtlowicz about radius-critical graphs to characterize graphs where the independence number is equal to the radius, for all possible values of the radius except 2, 3, and 4. We briefly discuss these remaining cases as well.

• 出版日期2012-5