A Characterization of Graphs Where the Independence Number Equals the Radius

被引：0

作者：

Ermelinda DeLaViña

Craig E. Larson

Ryan Pepper

Bill Waller

机构：

[1] University of Houston-Downtown,

[2] Virginia Commonwealth University,undefined

来源：

Graphs and Combinatorics | 2012年 / 28卷

关键词：

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

D O I：

暂无

中图分类号：

学科分类号：

摘要：

In a classical 1986 paper by Erdös, Saks and Saós 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.

引用

页码：315 / 332

页数：17

共 13 条

[1]

Bacsa’o G.(1990)A characterization of graphs without long induced paths J. Graph Theory 14 455-464

[2]

Tuza Z.(1986)Maximum induced trees in graphs J. Graph Theory 41 61-79

[3]

Erdös P.(1986)On two conjectures of Graffiti Congressus Numerantium 55 51-56

[4]

Saks M.(1988)A characterization of radius-critical graphs J. Graph Theory 12 529-532

[5]

Sa’os V.(1990)Some results on conjectures of Graffiti—1 Ars Comb. 29 90-106

[6]

Fajtlowicz S.(1992)A mode k index theorem Invent. Math. 107 283-299

[7]

Waller W.(undefined)undefined undefined undefined undefined-undefined

[8]

Fajtlowicz S.(undefined)undefined undefined undefined undefined-undefined

[9]

Favaron O.(undefined)undefined undefined undefined undefined-undefined

[10]

Maha’eo M.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →