On graphs maximizing the zero forcing number

A subset Z of vertex set V(G) of a graph G is a zero forcing set of G if iteratively adding vertices to Z from V(G)∖Z that are the unique neighbor in V(G)∖Z of some vertex in Z, results in the entire V(G) of G. The zero forcing number Z(G) of G is the minimum cardinality of a zero forcing set of G....

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2023-07, Vol.334, p.81-90
Main Authors: Liang, Yi-Ping, Xu, Shou-Jun
Format: Article
Language:English
Subjects:
Characterization
Extremal graphs
Upper bound
Zero forcing number
Zero forcing set
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A subset Z of vertex set V(G) of a graph G is a zero forcing set of G if iteratively adding vertices to Z from V(G)∖Z that are the unique neighbor in V(G)∖Z of some vertex in Z, results in the entire V(G) of G. The zero forcing number Z(G) of G is the minimum cardinality of a zero forcing set of G. In a recent work, Caro and Pepper (2015) proved that Z(G)≤(Δ−2)n−(Δ−δ)+2Δ−1, where n,Δ,δ are the order, maximum degree, minimum degree of G, respectively. In this paper we completely characterize extremal graphs attained the upper bound, solving a problem proposed by Lu et al. (2016). Our result further generalizes the characterization of extremal regular graphs obtained by Gentner et al. and Lu et al. in 2016.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2023.03.011