New bounds on the independence number of connected graphs.

Rad, Nader Jafari; Sharifi, Elahe

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öwenstein 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 3 n − 1 4 m. In this paper, we strengthen the above bound for connected graphs with maximum degree at least three that have a non-cut-vertex 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 3 n − 1 4 (m − Δ (G)) − 1 1 1 2 , 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 3 n − 1 4 (m − Δ (G)) − 2 3 .

MATHEMATICAL bounds; GEOMETRIC vertices; GRAPH connectivity; TRIANGLES; PLANAR graphs

Discrete Mathematics, Algorithms & Applications, 2018, Vol 10, Issue 5, pN.PAG

1793-8309

Academic Journal

10.1142/S1793830918500696