Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/1728
Title: | The zero forcing number of expanded paths and cycles | Authors: | Liao, Yipeng Chen, Chaohui Wei, Jia Stanić, Zoran |
Affiliations: | Numerical Mathematics and Optimization | Issue Date: | 2025 | Rank: | M23 | Publisher: | Union Matematica Argentina | Journal: | Revista de la Unión Matemática Argentina | Abstract: | The zero forcing number is defined as the minimum size of a zero forcing set, and features as an upper bound for the graph nullity. An expanded path $Pm_1,m_2,...,m_k$ (resp. expanded cycle $Cm_1,m_2,...,m_k$ ) is obtained from the $k$-vertex path (cycle) by replacing the $i$th vertex with an independent set of $m_i$ vertices. We prove that the zero forcing number of $Pm_1,m_2,...,m_k$ (resp. $Cm_1,m_2,...,m_k$ ) belongs to ${n−k, n−k+1} ({n−k+1, n−k+2})$, where $n$ is the number of vertices. It is also decided for which expanded paths and expanded cycles the zero forcing number is $n − k + 1$. As an application, we offer a new proof of the result of Liang, Li and Xu that gives a characterization of triangle-free graphs with zero forcing number $n − 3$. We also show that the zero forcing number of a cycle-spliced graph (i.e., a connected graph whose every block is a cycle) is $c + 1$, where $c$ is the cyclomatic number. This result induces an upper bound for the nullity of a cycle-spliced graph and extends the result of Wong, Zhou and Tian concerning the bipartite case. |
URI: | https://research.matf.bg.ac.rs/handle/123456789/1728 | ISSN: | 1669-9637 | DOI: | 10.33044/revuma.5022 |
Appears in Collections: | Research outputs |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.