Well-failed graphs

Bonnie C. Jacob · 2025

Read Well-failed graphs by Bonnie C. Jacob (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19357.txt.

Introduction

Bonnie C Jacob wrote a 2025 mathematics paper that opens the study of well-failed graphs. The setting is zero forcing, a game-like process where coloured vertices spread colour by a rule. A failed set is one that never manages to colour the whole graph, however the process runs.

A graph is well-failed when every maximal failed set is already a maximum one. The paper characterizes exactly which trees have this tidy property. Along the way it proves that the vertices missing from all minimal forts match those missing from all minimal forcing sets. That result pins down which tree vertices can never start a stalling pattern.

Catalog record

CREATORBonnie C. Jacob
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-19357

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Well-failed graphs Bonnie C. Jacob Abstract In this paper we begin the study of well-failed graphs, that is, graphs in which every maximal failed zero forcing set is a maximum failed zero forcing set, or equivalently, in which every minimal fort is a minimum fort. We characterize trees that are well-failed. Along the way, we prove that the set of vertices in a graph that are not in any minimal fort is identical to the set of vertices that are in no minimal zero forcing set, which allows us to characterize vertices in a tree that are in no minimal fort. 1 Introduction Over the past decade and a half, interest in the area of zero forcing has boomed. Introduced because of its applications to combinatorial matrix theory [ 1 ] and control of quantum systems [ 7 , 8 ] , zero forcing picked up interest since its introduction and led to the introduction of several related concepts, including failed zero forcing, forts, and zero blocking, which are intimately connected to each other and are all addressed in this paper. More information on the background of zero forcing can be found in [ 17 ] . A separate graph theoretic concept is the idea of well- X graphs, where X is a particular type of set. A well- X graph is a graph in which every minimal (or maximal, depending on X ) X set has the same cardinality. For example, well-covered graphs are graphs in which every maximal independent set has the same cardinality [ 16 , 18 ] , and well-dominated graphs are graphs in which every minimal dominating set has the same cardinality [ 2 , 14 ] . In [ 15 ] , the authors applied the “well” idea to zero forcing. In this paper, we introduce well-failed graphs, which are graphs in which every maximal failed zero forcing set is maximum. In doing so, we answer equivalent questions related to other parameters, most notably which graphs have the property that every minimal fort is minimum. We characterize trees that are well-failed, and along the way, characterize vertices in a tree that are in no minimal fort, or equivalently, in every maximal failed zero forcing set. We establish that in any graph the set of vertices that are in every maximal failed zero forcing set is the same as the set of vertices that are in no minimal zero forcing set. 1.1 Definitions and notation Throughout this paper, we assume all graphs are simple (no loops or multiple edges), undirected, and finite. Given a graph G , the vertex set is denoted V(G) and the edge set E(G) . If uv\in E(G) for u,v\in V(G) , then we say that u is a neighbor of v , and vice versa. The open neighborhood of v , denoted N(v) , is the set of neighbors of v , and the closed neighborhood of v , denoted N[v] is defined as N[v]=N(v)\cup\{v\} . The degree of a vertex v is defined as \deg(v)=|N(v)| . For other standard graph theory terminology the reader may consult [ 9 ] . A pendent vertex or pendant is a vertex with degree one. We refer to a vertex v in a tree as a high-degree vertex if \deg(v)\geq 3 . If v,v^{\prime} are pendants with common neighbor w , then we refer to v and v^{\prime} as double pendants and say that w has a double pendant . While there are many variations of zero forcing, this paper focuses on standard zero forcing, first formally introduced in [ 1 ] . In standard zero forcing, hereafter referred to as simply “zero forcing,” a subset S of the vertex set V(G) is colored blue, and V(G)\backslash S is colored white. The following color change rule is then applied: if any blue vertex has exactly one white neighbor, then the white neighbor will change to blue. The color change rule is applied repeatedly until no color changes are possible. We call the set of blue vertices in the graph after no more color changes are possible the closure of S , denoted cl(S) . If cl(S)=V(G) , then S is a zero forcing set . The cardinality of a smallest zero forcing set is \operatorname{Z}(G) , the zero forcing number of the graph. Failed zero forcing and stalled sets were first introduced in [ 13 ] . A failed zero forcing set , or for short, a failed set is a set of vertices that is not a zero forcing set. A stalled set is a set of vertices S such that S\subsetneq V(G) and no color changes are possible from S . The maximum cardinality among all failed sets is called the failed zero forcing number of the graph, and is denoted \operatorname{F}(G) . A maximum failed zero forcing set is a failed zero forcing set that is of largest cardinality among all failed sets of G . That is, a maximum failed set S is a failed set of G with |S|=\operatorname{F}(G) . Note that every stalled set is a failed set, but not the other way around. Also, every maximum failed set is a stalled set. Definition 1.1 . A maximal failed set is a failed set S such that adding any vertex from V(G)\backslash S to S produces a set that is not a failed set. A maximum failed set is a maximal failed set but not the other way around. Also, every maximal failed set is a stalled set. A fort , first formally introduced in [ 11 , 12 ] , is a nonempty set of vertices W such that |N(v)\cap W|\neq 1 for any vertex v with v\in V(G)\backslash W . That is, a fort is the complement of a stalled set, though forts and stalled sets were introduced independently. For forts and stalled sets, we use minimality and maximality differently than we do for failed sets. Definition 1.2 . A maximal stalled set is a stalled set that is not a proper subset of a stalled set. Similarly, a minimal fort is a fort that does not contain another fort as a proper subset. That is, for forts and stalled sets we use minimality and maximality with respect to inclusion. A zero blocking set , which is the complement of a failed set, was defined [ 3 ] . We stay with the terminology of failed zero forcing and forts in this paper, but include mention of zero blocking sets for completeness. A minimal zero blocking set is the complement of a maximal failed set: it is a zero blocking set such that if we remove any vertex from it, it is no longer a zero blocking set. 1.2 Preliminaries and basic results In this paper, we are interested in determining which graphs have the special property that every maximal failed set is a maximum failed set. We could also ask on which graphs every minimal fort is also a minimum fort, or a similar question for stalled and zero blocking sets, but it turns out that these questions are actually all equivalent as shown in the following lemma. Lemma 1.3 . The following are

Read the complete text