Independence number in graphs and its upper bounds

Shaveisi, Farzad

doi:10.22103/jmmr.2024.23302.1622

Independence number in graphs and its upper bounds

Document Type : Research Paper

Author

Farzad Shaveisi

Department of Mathematics, Faculty of Science, Razi University, Kermanshah, Iran

10.22103/jmmr.2024.23302.1622

Abstract

‎In this paper, we use the double counting method to find some upper bounds for the independence number of a simple graph in terms of its order, size and maximum degree. Moreover, we determine extremal graphs attaining equality in upper bounds. In addition, some lower bounds for the energy of graphs in terms of their size and maximum degree and the number of odd cycle, are determined.

Keywords

Independence number

Maximum degree

Edge

Energy

Subjects

Combinatorics, Graph, Coding and Cryptography

[1] Borg, P. A sharp upper bound for the independence number, 1{12. http://arxiv.orgarXiv:1007.5426v2.

[2] Cvetkovic, D., Rowlinson, P., & Simic, S. (2010). An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge.

[3] Gutman, I., The energy of a graph, Ber. Math.-Stat. Sekt. Forsch-Zent. Graz 103 (1978) 1{22. https://doi.org/10.4236/apm.2017.76021

[4] Suil, O., Yongtang S., & Zheny T (2021). Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree, Graphs Combin. 37, 393{408. https://doi.org/10.1007/s00373-020-02244-y

[5] Li, X., Shi, Y., & Gutman, I. (2012), Graph Energy, Springer-Verlag, New York.

[6] Wang, L., & Ma, X. (2017), Bounds of graph energy in terms of vertex cover number, Linear Algebra Appl. 517, 207{216. https://doi.org/10.1016/j.laa.2016.12.015

[7] West, D. B. (2001) Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River.