Zero Forcing with Random Sets

2022/08/27 by Bryan Curtis, Curtis, Bryan, Luyining Gan +7 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.2208.12899

Abstract

Given a graph G and a real number 0≤ p≤ 1, we define the random set B_p(G)⊂ V(G) by including each vertex independently and with probability p. We investigate the probability that the random set B_p(G) is a zero forcing set of G. In particular, we prove that for large n, this probability for trees is upper bounded by the corresponding probability for a path graph. Given a minimum degree condition, we also prove a conjecture of Boyer et. al. regarding the number of zero forcing sets of a given size that a graph can have.

Cited by

• The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction

Related

• Zero Forcing Number of Random Regular Graphs
• Probabilistic Zero Forcing in Graphs
• Exploring the Influence of Graph Operations on Zero Forcing Sets
• Zero forcing number of graphs
• Probabilistic Zero Forcing on Random Graphs