An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i>
For a given a graph <i>G</i>, the zero forcing number of <i>G</i>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>Z</mi><mo>(</mo><mi>G</mi>...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-09-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/19/4068 |
| _version_ | 1797575509037547520 |
|---|---|
| author | Chirag Kaudan Rachel Taylor Darren A. Narayan |
| author_facet | Chirag Kaudan Rachel Taylor Darren A. Narayan |
| author_sort | Chirag Kaudan |
| collection | DOAJ |
| description | For a given a graph <i>G</i>, the zero forcing number of <i>G</i>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>Z</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, is the smallest cardinality of any set <i>S</i> of vertices on which repeated applications of the forcing rule results in all vertices being included in <i>S</i>. The forcing rule is as follows: if a vertex <i>v</i> is in <i>S</i>, and exactly one neighbor <i>u</i> of <i>v</i> is not in <i>S</i>, then <i>u</i> is added to <i>S</i> in the next iteration. The failed zero forcing number of a graph was introduced by Fetcie, Jacob, and Saavedra and was defined as the cardinality of the largest set of vertices which fails to force all vertices in the graph. In 2021, Gomez et al. proved that there were exactly 15 graphs with a failed zero forcing number of two, but their proof was complicated, requiring the analysis of many graph families. We present an “inverse” approach where we start with a set of vertices <i>S</i> and then see which graphs have <i>S</i> as a maximum-sized failed zero forcing set. This results in not only a shorter proof but characterizes which graphs have a particular failed zero forcing set. In our proof, we characterize the graphs which have a failed zero forcing set <i>S</i> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>|</mo><mi>S</mi><mo>|</mo><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula>, meaning considering all simple graphs of order two as induced subgraphs. This approach also has greater potential for characterizing graphs where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>F</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>></mo><mn>2</mn></mrow></semantics></math></inline-formula> since many general arguments on the structure of graphs are developed in this type of analysis and are applicable for failed zero forcing sets of any size. |
| first_indexed | 2024-03-10T21:40:36Z |
| format | Article |
| id | doaj.art-3e6d5b003db54036bb3e483b6aecfedf |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T21:40:36Z |
| publishDate | 2023-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-3e6d5b003db54036bb3e483b6aecfedf2023-11-19T14:42:56ZengMDPI AGMathematics2227-73902023-09-011119406810.3390/math11194068An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i>Chirag Kaudan0Rachel Taylor1Darren A. Narayan2Department of Computer Science, San José State University, San Jose, CA 95192, USADeapartment of Mathematical Sciences, DePaul University, Chicago, IL 60614, USASchool of Mathematical and Statistics, Rochester Institute of Technology, Rochester, NY 14623, USAFor a given a graph <i>G</i>, the zero forcing number of <i>G</i>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>Z</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, is the smallest cardinality of any set <i>S</i> of vertices on which repeated applications of the forcing rule results in all vertices being included in <i>S</i>. The forcing rule is as follows: if a vertex <i>v</i> is in <i>S</i>, and exactly one neighbor <i>u</i> of <i>v</i> is not in <i>S</i>, then <i>u</i> is added to <i>S</i> in the next iteration. The failed zero forcing number of a graph was introduced by Fetcie, Jacob, and Saavedra and was defined as the cardinality of the largest set of vertices which fails to force all vertices in the graph. In 2021, Gomez et al. proved that there were exactly 15 graphs with a failed zero forcing number of two, but their proof was complicated, requiring the analysis of many graph families. We present an “inverse” approach where we start with a set of vertices <i>S</i> and then see which graphs have <i>S</i> as a maximum-sized failed zero forcing set. This results in not only a shorter proof but characterizes which graphs have a particular failed zero forcing set. In our proof, we characterize the graphs which have a failed zero forcing set <i>S</i> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>|</mo><mi>S</mi><mo>|</mo><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula>, meaning considering all simple graphs of order two as induced subgraphs. This approach also has greater potential for characterizing graphs where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>F</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>></mo><mn>2</mn></mrow></semantics></math></inline-formula> since many general arguments on the structure of graphs are developed in this type of analysis and are applicable for failed zero forcing sets of any size.https://www.mdpi.com/2227-7390/11/19/4068zero forcingfailed zero forcing |
| spellingShingle | Chirag Kaudan Rachel Taylor Darren A. Narayan An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i> Mathematics zero forcing failed zero forcing |
| title | An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i> |
| title_full | An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i> |
| title_fullStr | An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i> |
| title_full_unstemmed | An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i> |
| title_short | An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of <i>k</i> |
| title_sort | inverse approach for finding graphs with a failed zero forcing number of i k i |
| topic | zero forcing failed zero forcing |
| url | https://www.mdpi.com/2227-7390/11/19/4068 |
| work_keys_str_mv | AT chiragkaudan aninverseapproachforfindinggraphswithafailedzeroforcingnumberofiki AT racheltaylor aninverseapproachforfindinggraphswithafailedzeroforcingnumberofiki AT darrenanarayan aninverseapproachforfindinggraphswithafailedzeroforcingnumberofiki AT chiragkaudan inverseapproachforfindinggraphswithafailedzeroforcingnumberofiki AT racheltaylor inverseapproachforfindinggraphswithafailedzeroforcingnumberofiki AT darrenanarayan inverseapproachforfindinggraphswithafailedzeroforcingnumberofiki |