Zero Forcing and Vertex Independence Number on Cubic and Subcubic Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915001449578496 |
|---|---|
| author | Schuerger, Houston Warnberg, Nathan Young, Michael |
| author_facet | Schuerger, Houston Warnberg, Nathan Young, Michael |
| contents | Motivated by a conjecture from the automated conjecturing program TxGraffiti, in this paper the relationship between the zero forcing number, $Z(G)$, and the vertex independence number, $α(G)$, of cubic and subcubic graphs is explored. TxGraffiti conjectures that for all connected cubic graphs $G$, that are not $K_4$, $Z(G) \leq α(G) + 1$. This work uses decycling partitions of upper-embeddable graphs to show that almost all cubic graphs satisfy $Z(G) \leq α(G) + 2$, provides an infinite family of cubic graphs where $Z(G) = α(G) + 1$, and extends known bounds to subcubic graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21724 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Zero Forcing and Vertex Independence Number on Cubic and Subcubic Graphs Schuerger, Houston Warnberg, Nathan Young, Michael Combinatorics Motivated by a conjecture from the automated conjecturing program TxGraffiti, in this paper the relationship between the zero forcing number, $Z(G)$, and the vertex independence number, $α(G)$, of cubic and subcubic graphs is explored. TxGraffiti conjectures that for all connected cubic graphs $G$, that are not $K_4$, $Z(G) \leq α(G) + 1$. This work uses decycling partitions of upper-embeddable graphs to show that almost all cubic graphs satisfy $Z(G) \leq α(G) + 2$, provides an infinite family of cubic graphs where $Z(G) = α(G) + 1$, and extends known bounds to subcubic graphs. |
| title | Zero Forcing and Vertex Independence Number on Cubic and Subcubic Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.21724 |