More Like this

1. An Inverse Approach for Finding Graphs with a Failed Zero Forcing Number of k

   https://doi.org/10.3390/math11194068  

   Kaudan, Chirag; Taylor, Rachel; Narayan, Darren A. (October 2023, Mathematics)

   For a given a graph G, the zero forcing number of G, Z(G), is the smallest cardinality of any set S of vertices on which repeated applications of the forcing rule results in all vertices being included in S. The forcing rule is as follows: 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. 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 S and then see which graphs have S 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 S where |S|=2, meaning considering all simple graphs of order two as induced subgraphs. This approach also has greater potential for characterizing graphs where F(G)>2 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. 

   more » « less
2. All Graphs with a Failed Zero Forcing Number of Two

   https://doi.org/10.3390/sym13112221  

   Gomez, Luis; Rubi, Karla; Terrazas, Jorden; Narayan, Darren A. (November 2021, Symmetry)

   Given a graph G, the zero forcing number of G, Z(G), is the smallest cardinality of any set S of vertices on 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. 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 S that does not force all of the vertices in a graph to be in S. This quantity is known as the failed zero forcing number of a graph and will be denoted by F(G). We present new results involving this parameter. In particular, we completely characterize all graphs G where F(G)=2, solving a problem posed in 2015 by Fetcie, Jacob, and Saavedra. 

   more » « less
3. Failed zero forcing and critical sets on directed graphs

   Adams, Alyssa; Jacob, Bonnie (October 2021, The Australasian journal of combinatorics)

   Let $$D$$ be a simple digraph (directed graph) with vertex set $V(D)$ and arc set $A(D)$ where $n=|V(D)|$, and each arc is an ordered pair of distinct vertices. If $$(v,u) \in A(D)$$, then $$u$$ is considered an \emph{out-neighbor} of $$v$$ in $$D$$. Initially, we designate each vertex to be either filled or empty. Then, the following color change rule (CCR) is applied: if a filled vertex $$v$$ has exactly one empty out-neighbor $$u$$, then $$u$$ will be filled. If all vertices in $V(D)$$ are eventually filled under repeated applications of the CCR, then the initial set is called a \emph{zero forcing set} (ZFS); if not, it is a \emph{failed zero forcing set} (FZFS). We introduce the \emph{failed zero forcing number} $$\F(D)$$ on a digraph, which is the maximum cardinality of any FZFS. The \emph{zero forcing number}, $$\Z(D)$, is the minimum cardinality of any ZFS. We characterize digraphs that have $$\F(D)<\Z(D)$$ and determine $$\F(D)$$ for several classes of digraphs including de Bruijn and Kautz digraphs. We also characterize digraphs with $$\F(D)=n-1$$, $$\F(D)=n-2$$, and $$\F(D)=0$$, which leads to a characterization of digraphs in which any vertex is a ZFS. Finally, we show that for any integer $$n \geq 3$$ and any non-negative integer $$k$$ with $k 

   more » « less
4. An integer program for positive semidefinite zero forcing in graphs

   https://doi.org/10.1002/net.21947  

   Smith, Logan A.; Mikesell, Derek J.; Hicks, Illya V. (May 2020, Networks)

   Abstract Positive semidefinite (PSD) zero forcing is a dynamic graph process in which an initial subset of vertices are colored and may cause additional vertices to become colored through a set of color changing rules. Subsets which cause all other vertices to become colored are called PSD zero forcing sets; the PSD zero forcing number of a graph is the minimum cardinality attained by its PSD zero forcing sets. The PSD zero forcing number is of particular interest as it bounds solutions for the minimum rank and PSD min rank problems, both popular in linear algebra. This paper introduces blocking sets for PSD zero forcing sets which are used to formulate the first integer program (IP) for computing PSD zero forcing numbers of general graphs. It is shown that facets of the feasible region of this IP's linear relaxation correspond to zero forcing forts which induce connected subgraphs, but that identifying min cardinality connected forts is‐hard in general. Auxiliary IPs used to find these blocking sets are also given, enabling the master IP to be solved via constraint generation. Experiments comparing the proposed methods and existing algorithms are provided demonstrating improved runtime performance, particularly so in dense and sparse graphs. 

   more » « less
5. Short Proof of the Asymptotic Confirmation of the Faudree-Lehel Conjecture

   https://doi.org/10.37236/11413  

   Przybyło, Jakub; Wei, Fan (October 2023, The Electronic Journal of Combinatorics)

   Given a simple graph $$G$$, the irregularity strength of $$G$$, denoted $s(G)$, is the least positive integer $$k$$ such that there is a weight assignment on edges $$f: E(G) \to \{1,2,\dots, k\}$$ for which each vertex weight $$f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$$ is unique amongst all $$v\in V(G)$$. In 1987, Faudree and Lehel conjectured that there is a constant $$c$$ such that $$s(G) \leq n/d + c$$ for all $$d$$-regular graphs $$G$$ on $$n$$ vertices with $d>1$, whereas it is trivial that $$s(G) \geq n/d$$. In this short note we prove that the Faudree-Lehel Conjecture holds when $$d \geq n^{0.8+\epsilon}$$ for any fixed $$\epsilon >0$$, with a small additive constant $c=28$ for $$n$$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $$\beta\in(0,1/4)$$ there is a constant $$C$$ such that for all $$d$$-regular graphs $$G$$, $$s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$$, extending and improving a recent result of Przybyło that $$s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$$ whenever $$d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$$ and $$n$$ is large enough. 

   more » « less