Circles and line segments as independence attractors of graphs

Garima Khetawat, Moumita Manna, Tarakanta Nayak · 2025

Read Circles and line segments as independence attractors of graphs by Garima Khetawat, Moumita Manna, Tarakanta Nayak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20898.txt.

Introduction

Garima Khetawat, Moumita Manna, and Tarakanta Nayak study limiting shapes built from graph polynomials in this two thousand twenty-five mathematics paper. For a graph, the independence polynomial counts independent sets, sets of mutually non-adjacent vertices, by size. Taking repeated lexicographic products of the graph with itself and tracking where the polynomial's zeros accumulate yields the graph's independence attractor. The authors focus on attractors with simple topology.

They prove the attractor can never be a circle. If the attractor is a line segment, it must have a specific form, stretching from zero leftward to a point determined by one of a few small integers. They also supply examples of graphs with independence number four whose attractors are indeed line segments. The work fits into a broader program of understanding fractal-like zero distributions of graph polynomials through self-similar constructions.

Catalog record

CREATORGarima Khetawat, Moumita Manna, Tarakanta Nayak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-20898

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Circles and line segments as independence attractors of graphs Garima Khetawat, Moumita Manna, Tarakanta Nayak Abstract By an independent set in a simple graph G G , we mean a set of pairwise non-adjacent vertices in G G . The independence polynomial of G G is defined as I G ​ ( z ) = a 0 + a 1 ​ z + a 2 ​ z 2 + ⋯ + a α ​ z α I_{G}(z)=a_{0}+a_{1}z+a_{2}z^{2}+\cdots+a_{\alpha}z^{\alpha} , where a i a_{i} is the number of independent sets in G G with cardinality i i and α \alpha is the cardinality of a largest independent set in G G , known as the independence number of G G . Let G m G^{m} denote the m m -times lexicographic product of G G with itself. The independence attractor of G G , denoted by 𝒜 ⁡ ( G ) \mathscr{A}(G) , is defined as 𝒜 ⁡ ( G ) = lim m → ∞ { z : I G m ​ ( z ) = 0 } \mathscr{A}(G)=\lim_{m\rightarrow\infty}\{z:I_{G^{m}}(z)=0\} , where the limit is taken with respect to the Hausdorff metric on the space of all compact subsets of the plane. This paper deals with independence attractors that are topologically simple. It is shown that 𝒜 ⁡ ( G ) \mathscr{A}(G) can never be a circle. If 𝒜 ⁡ ( G ) \mathscr{A}(G) is a line segment then it is proved that the line segment is [ − 4 k , 0 ] [-\frac{4}{k},0] for some k ∈ { 1 , 2 , 3 , 4 } k\in\{1,2,3,4\} . Examples of graphs with independence number four are provided whose independence attractors are line segments. Key words: Independence polynomials, Independence attractors, Line segments, Graphs AMS Subject Classification: 37F20; 37F10; 05C69; 05C31 1 Introduction Let G be a simple graph, i.e., without a loop or a parallel edge with the vertex set V(G) and the edge set E(G) . Two vertices u and v of G are said to be adjacent, we denote it by u\sim v , if there is an edge between u and v . An independent set in G is a set of pairwise non-adjacent vertices in it. By an i -independent set , we mean an independent set with cardinality i . Let a_{i} be the number of i -independent sets in G . The independence polynomial of G is defined as I_{G}(z)=a_{0}+a_{1}z+a_{2}z^{2}+\cdots+a_{\alpha}z^{\alpha} , where \alpha is the cardinality of a largest independent set ( [ 8 ] ). The number \alpha is called the independence number of the graph G . For every graph G , a_{0}=1 , as the empty set is the only independent set with no element. Similarly, a_{1} is the number of vertices in G as each vertex constitutes an independent set with cardinality one. Further, a_{i}\neq 0 for all i=2,3,\ldots,\alpha . By an empty graph, we mean a graph with no edge but with at least one vertex. The independence polynomial of an empty graph with n vertices is 1+nz+\binom{n}{2}z^{2}+\binom{n}{3}z^{3}\cdots+\binom{n}{n}z^{n} . By a graph, we mean a non-empty graph unless stated otherwise. The roots of an independence polynomial, also called independence roots of a graph, are important. Their nature and location have been studied by many researchers. Csikvari proved that, for every graph, the independence root with smallest modulus is a negative real number [ 7 ] . In [ 6 ] , it is shown that all the independence roots of a claw-free graph are real. Considering specific families of graphs, Brown et al. proved that independence roots are dense in the plane. The independence roots of paths are dense in (-\infty,-\frac{1}{4}] [ 5 ] . We are concerned with the limit set of independence roots of a sequence of graphs arising out of lexicographic product. Given two graphs G and H , the lexicographic product ( or composition ) of G with H , denoted by G[H] , is defined as the graph with vertex set V(G[H])=V(G)\times V(H) , where V(G) and V(H) denote the vertex sets of G and H respectively. Two vertices (u,v) and (u^{\prime},v^{\prime}) in V(G[H]) are adjacent in G[H] if and only if either u\sim u^{\prime} in G , or u=u^{\prime} and v\sim v^{\prime} in H . This amounts to replacing each vertex of G with a copy of H and joining two vertices of two different copies according to the adjacency of vertices of G . The m -times lexicographic product of a graph G with itself is denoted by G^{m} . For a polynomial f , let \text{Roots}(f) denote the set of all its roots, i.e., \text{Roots}(f)=\{z:f(z)=0\} . The set \text{Roots}(I_{G^{m}}) is finite and therefore a compact subset of the plane for each m . The limit of \text{Roots}(I_{G^{m}}) exists as m\to\infty with respect to the Hausdorff metric (see Section 2 ), and is called the independence attractor \mathscr{A}(G) of the graph G [ 4 ] . A key fact relating the lexicographic product of a graph with itself and its independence polynomial is given by I_{G^{2}}(z)=I_{G}(I_{G}(z)-1) (see Theorem 1.1, [ 3 ] ). Denoting the reduced independence polynomial I_{G}(z)-1 of G by P_{G}(z) , note that I_{G^{2}}(z)=P_{G}(P_{G}(z))+1=P_{G}^{2}(z)+1 , and in general, I_{G^{m}}(z)=P_{G}^{m}(z)+1 . In other words, Roots(I_{G^{m}})=\{z:P_{G}^{m}(z)=-1\}\penalty\ \mbox{for all}\penalty\ m. (1.1) By virtue of this equality, the iterative behaviour of P_{G} assumes significance for investigating the independence attractor of G . This simple but very important fact gives rise to the following equivalent definition of the independence attractor. Definition 1.1 . \mathscr{A}(G)=\lim_{m\rightarrow\infty}P_{G}^{-m}(-1),\penalty\ \mbox{where }\penalty\ P_{G}^{-m}(-1)=\{z:P_{G}^{m}(z)=-1\} . The limit of P_{G}^{-m}(-1) as m\to\infty , usually referred to as independence fractal and denoted by \mathscr{F}(G) , has been a useful tool to understand the independence attractor of G . In fact, these two objects are the same except when -1 is a multiple root of I_{G} for every non-empty graph G . If -1 is a multiple root of I_{G} then \mathscr{A}(G) is a disjoint union of \mathscr{F}(G) and \cup_{m\geq 1}P_{G}^{-m}(-1) (see Theorem 2.9 ). The Julia set of a polynomial Q , denoted by \mathscr{J}(Q) , is defined as the boundary of its filled Julia set K(Q)=\{z:\{Q^{n}(z)\}_{n>0}\penalty\ \mbox{is bounded}\} . It is always a closed set. A very useful result obtained by Brown et al. states that \mathscr{F}(G)=\mathscr{J}(P_{G}) [ 3 ] and this is the basis of the proofs of our main results. We revisit these ideas and reproduce the proofs, often with additional explanations for the sake of completeness. Unlike [ 3 ] and [ 1 ] where independence fractal is the primary object of study, this article considers independence attractor as the main object and uses the idea of independence fractal to understand the former. For an empty graph (i.e., without any edge) G on n vertices, P_{G}(z)=(1+z)^{n}-1 and therefore, \mathscr{A}(G)=\{-1\} . For a complete graph K_{n} on n vertices, P_{K_{n}}(z)=nz and P^{-m}_{K_{n}}(-1)=-\frac{1}{n^{m}} . Thus, \mathscr{A}(K_{n})=\{0\} . This article deals with the independence attractors of graphs that are neither empty nor complete. Independence attractor of graphs with independence number two can be totally disconnected or connected ( [ 4 ] ). This article investigates the possibility of some topologically simple independence attractors, namely a circle or a line segment. The first possibility

Read the complete text