Back to Search
Start Over
Independence and upper irredundance in claw-free graphs
- Source :
-
Discrete Applied Mathematics . Oct2003, Vol. 132 Issue 1-3, p85. 11p. - Publication Year :
- 2003
-
Abstract
- It is known that the independence number of a connected claw-free graph <f>G</f> of order <f>n</f> is at most <f>(n+1)/2</f>. We improve this result by showing that this bound still holds for the upper irredundance number <f>IR(G)</f>. We characterize the connected claw-free graphs for which <f>IR(G)=(n+1)/2</f> and give some properties of those graphs for which <f>IR(G)=n/2</f> if <f>n</f> is even or <f>IR(G)=(n−1)/2</f> if <f>n</f> is odd. [Copyright &y& Elsevier]
- Subjects :
- *GRAPHIC methods
*GRAPH theory
*COMBINATORICS
*TOPOLOGY
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 132
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 11174468
- Full Text :
- https://doi.org/10.1016/S0166-218X(03)00392-5