Operations on covering numbers of certain graph classes
Abstract
The bounds on the sum and product of chromatic numbers of a graph and its complement are known as Nordhaus-Gaddum inequalities. In a similar way, the operations on the covering numbers of graphs with their complement are studied and with respect to this, new characterizations of certain graph classes have also been given in this paper.
About this article
Keywords
- Covering number
- graph complement
- independence number
- line graph
- matching number.
References
[1] M. Behzad, Graphs and their chromatic numbers, Doctoral Thesis, Michigan State University (1965).
[2] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, 2008.
[3] A. Brandstadt, V. B. Le and J. P. Spinrad, Graph Classes : A Survey, SIAM, Philadelphia, 1999.
[4] A E Brouwer, A. M Cohen and A Neumaier, Distance-Regular Graphs, Springer-Verlag, New York, 1989.
[5] G. Chartrand, P. Zhang, Chromatic Graph Theory, CRC Press, Western Michigan University Kalamazoo, MI, U.S.A.
[6] J. Clark and D. A. Holton, A First Look At Graph Theory, World Scientific, Singapore, 1991.
[7] K. L. Collins, A. Trenk, “Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number”, The electronic journal of combinatorics, 16(2009).
[8] N. Deo, Graph Theory with Applications to Engineering and Computer Science, PHI Learning, Delhi, 1974.
[9] R. Diestel, Graph Theory, Springer-Verlag, New York, 2000.
[10] J. A. Gallian, “A Dynamic survey of Graph Labeling”, The Electronic Journal of Combinatorics (DS-6), 2014.
[11] F. Harary, Graph Theory, Addison-Wesley Pub. Co. Inc., 1994.
[12] C. Susanth and S. J. Kalayathankal, “The Sum and Product of Independence Numbers of Graphs and Their Line Graphs”, Journal of Informatics and Mathematical Sciences, 6(2)(2014), 77-85.
[13] C. Susanth and S. J. Kalayathankal, “Operations on Independence Numbers of Certain Graph Classes”, communicated.
[14] V. G. Vizing, “Some unsolved problems in graph theory (in Russian)”, Uspekhi Mat. Nauk 23 (1968), 117–134., English translation in Russian Math. Surveys 23, 125–141.
[15] D. B. West, Introduction to Graph Theory, Pearson Education Asia,
2002.
[16] R. J. Wilson, Introduction to Graph Theory, Prentice Hall, 1998.
[17] Information System on Graph Classes and their Inclusions, http://www.graphclasses.org/smallgraphs.