Zero forcing number of a graph in terms of the number of pendant vertices
Xinlei Wang, Dein Wong, Yuanshuai Zhang · Linear and Multilinear Algebra · 2018
The zero forcing number of a graph has recently become an interesting graph parameter studied in its own right since its introduction by the ‘AIM Minimum Rank – Special Graphs Work Group’. In this article, we are interested in bounding the zero forcing number of a graph by the number of pendant vertices. Let p(G) and ϕ(G) be the number of pendant vertices and the cyclomatic number of G. If G is a connected graph with at least one edge that is not a cycle, then Z(G)≤p(G)+2ϕ(G)−1, the extremal graphs whose zero forcing number attain the upper bound are characterized. For a connected graph G with at least one edge that is not a path, we prove Z(G)≥p(G)−ω(G), where ω(G) is the number of similar equivalency classes of the set of all pendant vertices of G and two pendant vertices are said to be similar if they are the terminal vertices of a common major vertex. The extremal graphs with zero forcing number p(G)−ω(G) are also characterized.