On complementary graphs with no isolated vertices |
| |
Authors: | Renu Laskar Bruce Auerbach |
| |
Affiliation: | Clemenson University, Clemenson, SC 29631, U.S.A. |
| |
Abstract: | Let 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 . 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 , 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 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 等数据库收录! |
|