TY - JOUR
T1 - On the zero forcing number and propagation time of oriented graphs
AU - Hayat, Sakander
AU - Siddiqui, Hafiz Muhammad Afzal
AU - Imran, Muhammad
AU - Ikhlaq, Hafiz Muhammad
AU - Cao, Jinde
N1 - Funding Information:
S. Hayat and Muhammad Imran are supported by the University Program for Advanced Research (UPAR) by United Arab Emirates University (UAEU) under grant No. G00003271. The authors are grateful to the handling editor and the anonymous reviewer for a careful reading of this paper and for all their comments and remarks, which lead to a number of improvements of the paper.
Publisher Copyright:
© 2021 the Author(s), licensee AIMS Press.
PY - 2021
Y1 - 2021
N2 - Zero forcing is a process of coloring in a graph in time steps known as propagation time. These graph-theoretic parameters have diverse applications in computer science, electrical engineering and mathematics itself. The problem of evaluating these parameters for a network is known to be NP-hard. Therefore, it is interesting to study these parameters for special families of networks. Perila et al. (2017) studied properties of these parameters for some basic oriented graph families such as cycles, stars and caterpillar networks. In this paper, we extend their study to more non-trivial structures such as oriented wheel graphs, fan graphs, friendship graphs, helm graphs and generalized comb graphs. We also investigate the change in propagation time when the orientation of one edge is flipped.
AB - Zero forcing is a process of coloring in a graph in time steps known as propagation time. These graph-theoretic parameters have diverse applications in computer science, electrical engineering and mathematics itself. The problem of evaluating these parameters for a network is known to be NP-hard. Therefore, it is interesting to study these parameters for special families of networks. Perila et al. (2017) studied properties of these parameters for some basic oriented graph families such as cycles, stars and caterpillar networks. In this paper, we extend their study to more non-trivial structures such as oriented wheel graphs, fan graphs, friendship graphs, helm graphs and generalized comb graphs. We also investigate the change in propagation time when the orientation of one edge is flipped.
KW - Graph applications
KW - Graph coloring
KW - Oriented graphs
KW - Propagation time
KW - Zero forcing process
UR - http://www.scopus.com/inward/record.url?scp=85107802097&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85107802097&partnerID=8YFLogxK
U2 - 10.3934/math.2021111
DO - 10.3934/math.2021111
M3 - Article
AN - SCOPUS:85107802097
SN - 2473-6988
VL - 6
SP - 1833
EP - 1850
JO - AIMS Mathematics
JF - AIMS Mathematics
IS - 2
ER -