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


On complementary graphs with no isolated vertices
Authors:Renu Laskar  Bruce Auerbach
Affiliation:Clemenson University, Clemenson, SC 29631, U.S.A.
Abstract:Let G denote the complement of a graph G, and x(G), β1(G), β4(G), α0(G), α1(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order p, {2√p} ? x(G) + x(G) ? p + 1 and p ? x(G)·x(G) ? [(12(p + 1))2]. Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β1(G) + α1(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of G andG, since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both G andG contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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