New bounds on the independence number of connected graphs

Nader Jafari Rad | Elaheh Sharifi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=85633
Date :  2018/09/18
Publish in :    Discrete Mathematics, Algorithms and Applications
DOI :  https://doi.org/10.1142/s1793830918500696
Link :  http://dx.doi.org/10.1142/S1793830918500696
Keywords :bounds, graphs

Abstract :

---

The independence number of a graph G, denoted by α(G), is the maximum cardinality of an independent set of vertices in G. Henning and L¨owenstein An improved lower bound on the independence number of a graph, Discrete Applied Mathematics 179 (2014) 120– 128. proved that if a connected graph G of order n and size m does not belong to a specific family of graphs, then α(G) 2 3n− 1 4m. In this paper, we strengthen the above bound for connected graphs with maximum degree at least three that have a non-cutvertex of maximum degree. We show that if a connected graph G of order n and size m has a non-cut-vertex of maximum degree then α(G) ≥ 2 3n − 1 4 (m − Δ(G)) − 11 12, where Δ(G) is the maximum degree of the vertices of G. We also characterize all connected graphs G of order n and size m that have a non-cut-vertex of maximum degree and α(G) ≤ 2 3n − 1 4 (m − Δ(G)) − 2 3 .