首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号