Independence,irredundance, degrees and chromatic number in graphs |
| |
Affiliation: | 1. MTA SZTAKI, Hungarian Academy of Sciences, 1111 Budapest Kende u. 13-17, Hungary;2. LRI, Université Paris-Sud, Bat 490, 91405 Orsay Cedex, France |
| |
Abstract: | Let β(G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ≠0, IR(G)⩽n/(1+δ/Δ) and IR(G)−β(G)⩽((Δ−2)/2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ=3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)−β(G)⩽((χ−2)/2χ)n in any non-empty graph of order n⩾2. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|