On leaky forcing and resilience
Autor: | Michael Young, Joseph S. Alameda, Nathan Warnberg, Jürgen Kritschgau |
---|---|
Rok vydání: | 2022 |
Předmět: |
Vertex (graph theory)
Hardware_MEMORYSTRUCTURES Forcing (recursion theory) Quantitative Biology::Neurons and Cognition Applied Mathematics Mathematical analysis 0211 other engineering and technologies Order (ring theory) 021107 urban & regional planning 02 engineering and technology 010501 environmental sciences Grid 01 natural sciences Upper and lower bounds Set (abstract data type) FOS: Mathematics Hardware_INTEGRATEDCIRCUITS Zero Forcing Equalizer Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Resilience (materials science) 0105 earth and related environmental sciences Mathematics |
Zdroj: | Discrete Applied Mathematics. 306:32-45 |
ISSN: | 0166-218X |
Popis: | A leak is a vertex that is not allowed to perform a force during the zero forcing process. Leaky forcing was recently introduced as a new variation of zero forcing in order to analyze how leaks in a network disrupt the zero forcing process. The l -leaky forcing number of a graph is the size of the smallest zero forcing set that can force a graph despite l leaks. A graph G is l -resilient if its zero forcing number is the same as its l -leaky forcing number. In this paper, we analyze l -leaky forcing and show that if an ( l − 1 ) -leaky forcing set B is robust enough, then B is an l -leaky forcing set. This provides the framework for characterizing l -leaky forcing sets. Furthermore, we consider structural implications of l -resilient graphs. We apply these results to bound the l -leaky forcing number of several graph families including trees, supertriangles, and grid graphs. In particular, we resolve a question posed by Dillman and Kenter concerning the upper bound on the 1-leaky forcing number of grid graphs. |
Databáze: | OpenAIRE |
Externí odkaz: |