Zero forcing with random sets

DOI10.1016/J.DISC.2024.113944MaRDI QIDQ6204353zbMATH OpenOpenAlexFDO

Authors Bryan A. Curtis, Luyining Gan, Jamie Haddock, Rachel Lawrence, Sam Spiro

Publication date 27 March 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.12899

zbMATH Keywords

graph thresholdrandom graphsrandom set zero forcingzero forcing polynomial

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Given a graph $G$ and a real number $0leple1$, we define the random set $B_p(G)subsetV(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.

Recommendations

• Probabilistic zero forcing on random graphs
• Zero-forcing in random regular graphs
• Probalistic zero forcing in graphs
• The Zero Forcing Number of Graphs
• Minimal zero forcing sets

Cites work

• A technique for computing the zero forcing number of a graph with a cut-vertex
• Bounds on expected propagation time of probabilistic zero forcing
• Cores and shells of graphs.
• Introduction to Random Graphs
• Inverse Problems and Zero Forcing for Graphs
• Minimum rank of skew-symmetric matrices described by a graph
• Power domination in graphs
• Probabilistic zero forcing on random graphs
• Probalistic zero forcing in graphs
• Propagation time for probabilistic zero forcing
• The zero forcing polynomial of a graph
• Threshold functions
• Throttling zero forcing propagation speed on graphs
• Tight bounds on probabilistic zero forcing on hypercubes and grids
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs
• Zero-forcing in random regular graphs

Cited in

(1)

• Exploring the influence of graph operations on zero forcing sets

This page was built for publication: Zero forcing with random sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204353)