Independence number in graphs and its upper bounds

Document Type : Research Paper

Author

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

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

Main Subjects

References

[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.
Journal of Mahani Mathematical Research
Volume 14, Issue 1 - Serial Number 31
January 2025
Pages 399-405

Files

History

  • Receive Date: 30 April 2024
  • Revise Date: 11 October 2024
  • Accept Date: 11 November 2024

Share

How to cite

Statistics