Structural Classification of a Graph with Independence Number Five

2026/07/31 by Manisha Kumari, Dinesh Kumar
Mathematics · #math.CO #math.DS #msc:37F50 #msc:37F10 #msc:05C69 #msc:05C31

paper · pdf

17 pages. Comments are welcome

arxiv created 2026/07/31 · arxiv updated 2026/08/03

Abstract

The independence polynomial of a simple graph G is given by \( I_G(z) = i₀ + i₁ z + i₂ z² + ⋯ + i_αz^α\), where \( i_α\) denotes the size of a maximum independent set, also called the independence number of the graph. The independence polynomial has the notable feature of being essentially closed under graph composition (lexicographic product). In this paper, we determine the independence polynomials of size five. For a disconnected graph G, we exploit the fact that I_G(z) factors as the product of the independence polynomials of the connected components of G. Furthermore, we classify all independence polynomials that can occur for such a disconnected graph G and, by examining their component structures, we characterize the disconnected configurations that may arise.

Citations

• Connectedness of independence attractors of graphs with independence number three
• Circles and line segments as independence attractors of graphs