Circles and line segments as independence attractors of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912397518700544 |
|---|---|
| author | Khetawat, Garima Manna, Moumita Nayak, Tarakanta |
| author_facet | Khetawat, Garima Manna, Moumita Nayak, Tarakanta |
| contents | By an independent set in a simple graph $G$, we mean a set of pairwise non-adjacent vertices in $G$. The independence polynomial of $G$ is defined as $I_G(z)=a_0 + a_1 z + a_2 z^2+\cdots+a_αz^α$, where $a_i$ is the number of independent sets in $G$ with cardinality $i$ and $α$ is the cardinality of a largest independent set in $G$, known as the independence number of $G$. Let $G^m$ denote the $m$-times lexicographic product of $G$ with itself. The independence attractor of $G$, denoted by $\mathcal{A}(G)$, is defined as $\mathcal{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 $\mathcal{A}(G)$ can never be a circle. If $\mathcal{A}(G)$ is a line segment then it is proved that the line segment is $[-\frac{4}{k}, 0]$ for some $k \in \{1, 2, 3, 4 \}$. Examples of graphs with independence number four are provided whose independence attractors are line segments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_20898 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Circles and line segments as independence attractors of graphs Khetawat, Garima Manna, Moumita Nayak, Tarakanta Combinatorics Dynamical Systems 37F20, 37F10, 05C69, 05C31 By an independent set in a simple graph $G$, we mean a set of pairwise non-adjacent vertices in $G$. The independence polynomial of $G$ is defined as $I_G(z)=a_0 + a_1 z + a_2 z^2+\cdots+a_αz^α$, where $a_i$ is the number of independent sets in $G$ with cardinality $i$ and $α$ is the cardinality of a largest independent set in $G$, known as the independence number of $G$. Let $G^m$ denote the $m$-times lexicographic product of $G$ with itself. The independence attractor of $G$, denoted by $\mathcal{A}(G)$, is defined as $\mathcal{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 $\mathcal{A}(G)$ can never be a circle. If $\mathcal{A}(G)$ is a line segment then it is proved that the line segment is $[-\frac{4}{k}, 0]$ for some $k \in \{1, 2, 3, 4 \}$. Examples of graphs with independence number four are provided whose independence attractors are line segments. |
| title | Circles and line segments as independence attractors of graphs |
| topic | Combinatorics Dynamical Systems 37F20, 37F10, 05C69, 05C31 |
| url | https://arxiv.org/abs/2505.20898 |