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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Luis Gomez, Karla Rubi, Jorden Terrazas, Darren A. Narayan
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	failed zero forcing number zero forcing number graph labelling Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/382ff62de0fa4047bba6ee5af930ca60
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:382ff62de0fa4047bba6ee5af930ca60
record_format	dspace
spelling	oai:doaj.org-article:382ff62de0fa4047bba6ee5af930ca602021-11-25T19:07:43ZAll Graphs with a Failed Zero Forcing Number of Two10.3390/sym131122212073-8994https://doaj.org/article/382ff62de0fa4047bba6ee5af930ca602021-11-01T00:00:00Zhttps://www.mdpi.com/2073-8994/13/11/2221https://doaj.org/toc/2073-8994Given 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.Luis GomezKarla RubiJorden TerrazasDarren A. NarayanMDPI AGarticlefailed zero forcing numberzero forcing numbergraph labellingMathematicsQA1-939ENSymmetry, Vol 13, Iss 2221, p 2221 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	failed zero forcing number zero forcing number graph labelling Mathematics QA1-939
spellingShingle	failed zero forcing number zero forcing number graph labelling Mathematics QA1-939 Luis Gomez Karla Rubi Jorden Terrazas Darren A. Narayan All Graphs with a Failed Zero Forcing Number of Two
description	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.
format	article
author	Luis Gomez Karla Rubi Jorden Terrazas Darren A. Narayan
author_facet	Luis Gomez Karla Rubi Jorden Terrazas Darren A. Narayan
author_sort	Luis Gomez
title	All Graphs with a Failed Zero Forcing Number of Two
title_short	All Graphs with a Failed Zero Forcing Number of Two
title_full	All Graphs with a Failed Zero Forcing Number of Two
title_fullStr	All Graphs with a Failed Zero Forcing Number of Two
title_full_unstemmed	All Graphs with a Failed Zero Forcing Number of Two
title_sort	all graphs with a failed zero forcing number of two
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/382ff62de0fa4047bba6ee5af930ca60
work_keys_str_mv	AT luisgomez allgraphswithafailedzeroforcingnumberoftwo AT karlarubi allgraphswithafailedzeroforcingnumberoftwo AT jordenterrazas allgraphswithafailedzeroforcingnumberoftwo AT darrenanarayan allgraphswithafailedzeroforcingnumberoftwo
_version_	1718410270634672128

All Graphs with a Failed Zero Forcing Number of Two

Ejemplares similares