Leaky forcing and resilience of Cartesian products of K n K_{n}

Rebekah Herrman, Grace Wisdom · 2024

Read Leaky forcing and resilience of Cartesian products of K n K_{n} by Rebekah Herrman, Grace Wisdom (2024) 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-2411-03178.txt.

Description

Abstract . Zero forcing is a process on a graph G = ( V , E ) G=(V,E) in which a set of initially colored vertices, B 0 ​ ( G ) ⊂ V ​ ( G ) B_{0}(G)\subset V(G) , can color their neighbors according to the color change rule.

Catalog record

CREATORRebekah Herrman, Grace Wisdom
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-03178

Browse the full library · About the Tower of Babel

Full text

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

Leaky forcing and resilience of Cartesian products of K n K_{n} Rebekah Herrman, Grace Wisdom Abstract . Zero forcing is a process on a graph G = ( V , E ) G=(V,E) in which a set of initially colored vertices, B 0 ​ ( G ) ⊂ V ​ ( G ) B_{0}(G)\subset V(G) , can color their neighbors according to the color change rule. The color change rule states that if a vertex v v can color a neighbor u u if u u is the only uncolored neighbor of v v . If a vertex v v colors its neighbor, u u , v v is said to force u u . Leaky forcing is a recently introduced variant of zero forcing in which some vertices cannot force their neighbors, even if they satisfy the color change rule. This variation has been studied for limited families of graphs with particular structure, such as products of paths and discrete hypercubes. A concept closely related to ℓ \ell -leaky forcing is ℓ \ell -resilience. A graph is said to be ℓ \ell -resilient if its ℓ \ell -leaky forcing number equals its zero forcing number. In this paper, we prove direct products of K n K_{n} with P t P_{t} and K n K_{n} with C t C_{t} is 1-resilient and conjecture the former is not 2-resilient. Keywords: Leaky forcing; Cartesian product; Complete graphs; Resilience AMS subject classification: 68R10, 05C50, 05C57 1. Introduction Zero forcing is a vertex coloring process that has origins in quantum control theory [ 8 ] and applications to numerous fields such as network controllability [ 24 , 26 , 25 ] . In the zero forcing process on a graph G=(V,E) , a subset of vertices B\subset V(G) is initially colored blue. A blue vertex v can color an uncolored neighbor u , or v can force u , if u is the only uncolored neighbor of v . This is known as the color change rule . If the set B can eventually force all vertices of G , we say that B is a zero forcing set . The zero forcing number of G is denoted Z(G) and is equal to the size of the smallest cardinality zero forcing set. Previous work in zero forcing includes determining how long it takes for a zero forcing set to infect a graph [ 20 , 9 ] , degree-based bounds for the zero forcing number [ 16 , 12 ] , and approximation algorithms and machine learning models for finding zero forcing numbers and sets [ 10 , 2 ] . In 2019, Dillman, and Kenter introduced \ell -leaky forcing, a variation of zero forcing in which \ell vertices do not enforce the color change rule [ 13 ] . Z_{(\ell)}(G) is used to denote the \ell -leaky forcing number, which is the size of a smallest cardinality set that can force G even with the addition of \ell leaks. We shall call the set \ell -leaky forcing vertices B_{\ell} . Zero forcing is equivalent to \ell -leaky forcing when \ell=0 , thus, throughout this work we will use Z_{0}(G) to denote the zero forcing number of G and B_{0} to denote a minimum zero forcing set. Recent \ell -leaky forcing work includes exactly determining the \ell -leaky forcing number (or proving upper bounds) for some families of graphs [ 19 ] , different variations of \ell -leaky forcing [ 14 , 4 ] , applications in computer science [ 1 ] , and the introduction of \ell -resilience [ 3 ] . A graph G is said to be \ell -resilient if its \ell -leaky forcing number is equal to its zero forcing number. Products of graphs have gained significant attention in zero forcing [ 21 , 22 , 11 , 6 , 23 ] and other graph infection processes such as bootstrap percolation [ 7 , 15 , 17 , 18 ] . In this work, we first calculate the 1 -leaky forcing number of direct products of K_{n} with P_{t} , C_{t} , and itself in Sec. 2 . The direct product of two graphs G and H , denoted G\times H , is a graph with vertex set V(G)\times V(H) . Two vertices (g,h) and (g^{\prime},h^{\prime}) form an edge in G\times H if and only if gg^{\prime}\in E(G) and hh^{\prime}\in E(H) . In the same section, we conjecture that K_{n}\times P_{t} is not 2 -resilient. In Sec. 3 , we summarize the main results of this work and introduce related open questions. 2. 1 -resilience of direct products including K_{n} We first consider the 1 -leaky forcing number of paths on t vertices, P_{t} , with complete graphs on n vertices, K_{n} . Theorem 2.1 . K_{n}\times P_{t} is 1 -resilient. Specifically, Z_{1}(K_{n}\times P_{t})=Z_{0}(K_{n}\times P_{t})=\begin{cases}(n-2)t&t\;\mathrm{even},\;n\geq 3\\ (n-2)t+2&t\;\mathrm{odd},\;n\geq 2\end{cases}. Proof. Draw K_{n}\times P_{t} such that vertices are arranged in n rows and t columns. Label vertices such that the top left is (1,1) , bottom left is (n,1) , the top right is (1,t) and the bottom right is (n,t) . In general, the first coordinate of each vertex label refers to the row and the second coordinate refers to the column. Benson, Ferrero, Flagg, Furst, Hogben, Vasilevska, and Wissman [ 5 ] showed that Z_{0}(K_{n}\times P_{t})=\begin{cases}(n-2)t&t\;\mathrm{even},\;n\geq 3\\ (n-2)t+2&t\;\mathrm{odd},n\geq 2\end{cases}. Since Z_{(0)}(G)\leq Z_{(1)}(G), we need only construct sets of the appropriate sizes to show the result. Case 1: t even. We consider two subcases: n even and n odd. Subcase 1.1: n even. Let the initially infected set be vertices \{(i,1)\}_{i=3}^{n}\cup\{(j,t)\}_{j=1}^{n-2}\cup\{(f,2)\}_{f\notin\{1,n\}}\cup\{(m,2k)\}_{k\notin\{1,\frac{t}{2}\},m\notin\{\frac{n}{2},\frac{n}{2}+1\}}\cup\{(q,2p+1)\}_{p\neq 0,q\notin\{1,n\}} . Note that this set has size (n-2)t as each of the t columns contains exactly n-2 initially infected vertices. See Fig. 1 for an example of an initially infected set. There are two subcases to consider: there is a leak in column 1 or t , or there is a leak in what we will call an “interior column", that is a column that is not column 1 or t . Subcase 1.1.1: Leak in column 1 or t . Suppose there is a leak in column 1 , without loss of generality. Then the forcing process starts from column t . The vertex (1,t) forces (n,t-1) , and once this is forced, (2,t) forces (1,t-1) . Note then that (1,t-2) forces (n,t-3) and (n,t-2) forces (1,t-3) . Note that since there are no leaks until the first column, this process iterates until column 1 is forced, with even indexed columns 2p forcing odd indexed columns 2p-1 . Once all odd columns have been forced, note that there is at most 1 leak in column 1. This means either (1,1) can force (n,2) or (1,n) can force (1,2) , or both. Once either (n,2) or (1,2) is forced, the other is forced by any vertex (1,j) for j\in\{2,3,\ldots,n-1\} . Since columns 1 through 3 have all been forced, column 3 can then force column 4, and odd indexed columns 2q+1 force even indexed columns 2(q+1) until all vertices have been forced. If there is instead a leak in column t , a similar process occurs where odd-indexed columns force even-indexed columns until column t is forced, and then

Read the complete text