The independence number of a graph which is just the cardinality of a largest independent vertex set, i.e., the size of a maximum independent vertex set, is one of the many numbers associated with graphs and it has many applications in many problems including massive data sets, coding theory and wireless networks. Edge and vertex numbers are two of the most important graph parameters and most of the calculations related to graphs are done by means of them. Deleting vertices and edges naturally effects the calculations. In this work, it has been shown that the effect of these deletions also effect the independence number of graphs and these changes are calculated.

independence number, vertex deletion, edge deletion.

Received: December 3, 2021; Accepted: January 20, 2022; Published: January 31, 2022

How to cite this article: Sadik Delen, Fikriye Ersoy Zihni, Fatma Ozen Erdogan, Hacer Ozden Ayna and Ismail Naci Cangul, The effect of vertex and edge deletion on the independence number of graphs, Far East Journal of Applied Mathematics 112 (2022), 11-19. DOI: 10.17654/0972096022002

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License 

References:

[1] S. Delen and I. N. Cangul, A new graph invariant, Turkish Journal of Analysis and Number Theory 6(1) (2018), 30-33.
[2] S. Delen and I. N. Cangul, Extremal problems on components and loops in graphs, Acta Mathematica Sinica English Series 35(2) (2019), 161-171.
[3] S. Delen, A. Yurttas, M. Togan and I. N. Cangul, Omega invariant of graphs and cyclicness, Applied Sciences 21 (2019), 91-95.
[4] M. S. Oz and I. N. Cangul, Bounds for matching number of fundamental realizations according to graph invariant omega, Proceedings of the Jangjeon Mathematical Society 23(1) 2020, pp. 23-37.
[5] H. Ozden, F. Ersoy Zihni, F. Ozen Erdogan, I. N. Cangul, G. Srivastava and H. M. Srivastava, Independence number of graphs and line graphs of trees by means of omega invariant, Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales, Serie A. Matemáticas 114 (2020), 91.