Characterization of All Graphs with a Failed Skew Zero Forcing Number of 1

Aidan Johnson, Andrew E. Vick and Darren A. Narayan ()
Additional contact information
Aidan Johnson: School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA
Andrew E. Vick: Department of Mathematical Sciences, Lee University, Cleveland, TN 37311, USA
Darren A. Narayan: School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623, USA

Mathematics, 2022, vol. 10, issue 23, 1-9

Abstract: Given a graph G , the zero forcing number of G , Z ( G ) , is the minimum cardinality of any set S of vertices of which repeated applications of the forcing rule results in all vertices being in S . The forcing rule is: if a vertex v is in S , and exactly one neighbor u of v is not in S , then u is added to S in the next iteration. Hence the failed zero forcing number of a graph was defined to be the cardinality of the largest set of vertices which fails to force all vertices in the graph. A similar property called skew zero forcing was defined so that if there is exactly one neighbor u of v is not in S , then u is added to S in the next iteration. The difference is that vertices that are not in S can force other vertices. This leads to the failed skew zero forcing number of a graph, which is denoted by F − ( G ) . In this paper, we provide a complete characterization of all graphs with F − ( G ) = 1 . Fetcie, Jacob, and Saavedra showed that the only graphs with a failed zero forcing number of 1 are either: the union of two isolated vertices; P 3 ; K 3 ; or K 4 . In this paper, we provide a surprising result: changing the forcing rule to a skew-forcing rule results in an infinite number of graphs with F − ( G ) = 1 .

Keywords: zero forcing; skew zero forcing (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/23/4463/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/23/4463/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:23:p:4463-:d:984809

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().