Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2409.14576 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914954740760576 |
|---|---|
| author | Cutler, Jonathan Kahl, Nathan Zielonka, Phoebe |
| author_facet | Cutler, Jonathan Kahl, Nathan Zielonka, Phoebe |
| contents | The independence polynomial of a graph $G$ evaluated at $-1$, denoted here as $I(G;-1)$, has arisen in a variety of different areas of mathematics and theoretical physics as an object of interest. Engström used discrete Morse theory to prove that $\left|I(G;-1)\right|\leq 2^{ϕ(G)}$ where $ϕ(G)$ is the decycling number of $G$, i.e., the minimum number of vertices needed to be deleted from $G$ so that the remaining graph is acyclic. Here, we improve Engström's bound by showing $\left|I(G;-1)\right|\leq 2^{ϕ_3(G)}$ where $ϕ_3(G)$ is the minimum number of vertices needed to be deleted from $G$ so that the resulting graph contains no induced cycles whose length is divisible by $3$. We also note that this bound is not just sharp but that every value in the range given by the bound is attainable by some connected graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14576 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on the alternating number of independent sets in a graph Cutler, Jonathan Kahl, Nathan Zielonka, Phoebe Combinatorics The independence polynomial of a graph $G$ evaluated at $-1$, denoted here as $I(G;-1)$, has arisen in a variety of different areas of mathematics and theoretical physics as an object of interest. Engström used discrete Morse theory to prove that $\left|I(G;-1)\right|\leq 2^{ϕ(G)}$ where $ϕ(G)$ is the decycling number of $G$, i.e., the minimum number of vertices needed to be deleted from $G$ so that the remaining graph is acyclic. Here, we improve Engström's bound by showing $\left|I(G;-1)\right|\leq 2^{ϕ_3(G)}$ where $ϕ_3(G)$ is the minimum number of vertices needed to be deleted from $G$ so that the resulting graph contains no induced cycles whose length is divisible by $3$. We also note that this bound is not just sharp but that every value in the range given by the bound is attainable by some connected graph. |
| title | A note on the alternating number of independent sets in a graph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.14576 |