Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.01423 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910432371933184 |
|---|---|
| author | Menon, Krishna Singh, Anurag |
| author_facet | Menon, Krishna Singh, Anurag |
| contents | Zero forcing in graphs is a coloring process where a colored vertex can force its unique uncolored neighbor to be colored. A zero forcing set is a set of initially colored vertices capable of eventually coloring all vertices of the graph. In this paper, we focus on the numbers $z(G; i)$, which is the number of zero forcing sets of size $i$ of the graph $G$. These numbers were initially studied by Boyer et al. where they conjectured that for any graph $G$ on $n$ vertices, $z(G; i) \leq z(P_n; i)$ for all $i \geq 1$ where $P_n$ is the path graph on $n$ vertices. The main aim of this paper is to show that several classes of graphs, including outerplanar graphs and threshold graphs, satisfy this conjecture. We do this by studying various graph operations and examining how they affect the number of zero forcing sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01423 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exploring the Influence of Graph Operations on Zero Forcing Sets Menon, Krishna Singh, Anurag Combinatorics 05C05, 05C15, 05C30, 05C69 Zero forcing in graphs is a coloring process where a colored vertex can force its unique uncolored neighbor to be colored. A zero forcing set is a set of initially colored vertices capable of eventually coloring all vertices of the graph. In this paper, we focus on the numbers $z(G; i)$, which is the number of zero forcing sets of size $i$ of the graph $G$. These numbers were initially studied by Boyer et al. where they conjectured that for any graph $G$ on $n$ vertices, $z(G; i) \leq z(P_n; i)$ for all $i \geq 1$ where $P_n$ is the path graph on $n$ vertices. The main aim of this paper is to show that several classes of graphs, including outerplanar graphs and threshold graphs, satisfy this conjecture. We do this by studying various graph operations and examining how they affect the number of zero forcing sets. |
| title | Exploring the Influence of Graph Operations on Zero Forcing Sets |
| topic | Combinatorics 05C05, 05C15, 05C30, 05C69 |
| url | https://arxiv.org/abs/2405.01423 |