Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/s00373-011-1054-x | Graphs and Combinatorics |
Keywords | Field | DocType |
s. fajtlowicz,independence number,radius r,ciliate · bipartite number · forest number · independence number · path number · radius · scaffold · tree number,remaining case,induced path,radius-critical graph,possible value | Topology,Discrete mathematics,Graph,Indifference graph,Combinatorics,Independence number,Induced path,Chordal graph,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 3 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ermelinda Delavina | 1 | 23 | 4.51 |
Craig E. Larson | 2 | 15 | 4.55 |
ryan pepper | 3 | 40 | 6.80 |
Bill Waller | 4 | 8 | 2.54 |