All Graphs with a Failed Zero Forcing Number of Two
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...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
MDPI AG
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/382ff62de0fa4047bba6ee5af930ca60 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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 in <i>S</i>. The forcing rule is: 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. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. In this paper, we investigate the largest size of a set <i>S</i> that does not force all of the vertices in a graph to be in <i>S</i>. This quantity is known as the failed zero forcing number of a graph and will be denoted by <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></mrow></semantics></math></inline-formula>. We present new results involving this parameter. In particular, we completely characterize all graphs <i>G</i> 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>, solving a problem posed in 2015 by Fetcie, Jacob, and Saavedra. |
|---|