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

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.