On the zero forcing number and propagation time of oriented graphs

Sakander Hayat, Hafiz Muhammad Afzal Siddiqui, Muhammad Imran, Hafiz Muhammad Ikhlaq, Jinde Cao

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)1833-1850
Number of pages18
JournalAIMS Mathematics
Volume6
Issue number2
DOIs
Publication statusPublished - 2021

Keywords

  • Graph applications
  • Graph coloring
  • Oriented graphs
  • Propagation time
  • Zero forcing process

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On the zero forcing number and propagation time of oriented graphs'. Together they form a unique fingerprint.

Cite this