The Zero Forcing Number of Graphs

DOI10.1137/17M1133051MaRDI QIDQ4610449zbMATH OpenOpenAlexFDO

Authors Thomas Kalinowski, Nina Kamčev, Benny Sudakov

Publication date 16 January 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graphs with large girthrandom graphszero forcing sets

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A subset $S$ of initially infected vertices of a graph $G$ is called forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbour, infects this neighbour. The forcing number of $G$ is the minimum cardinality of a forcing set in $G$. In the present paper, we study the forcing number of various classes of graphs, including graphs of large girth, $H$-free graphs for a fixed bipartite graph $H$, random and pseudorandom graphs.

Recommendations

• Some bounds on the zero forcing number of a graph
• On graphs maximizing the zero forcing number
• On extremal graphs for zero forcing number
• The zero forcing polynomial of a graph
• The zero forcing number of graphs with the matching number and the cyclomatic number
• On Zero Forcing Number of Permutation Graphs
• On the zero forcing number of bijection graphs
• Proof of a conjecture on the zero forcing number of a graph
• On the zero forcing number of a graph involving some classical parameters

Cites work

• A lower bound on the zero forcing number
• A proof of Alon’s second eigenvalue conjecture and related problems
• A protocol for cooling and controlling composite systems by local interactions
• Anagram-free colourings of graphs
• Bounds for the Zero Forcing Number of Graphs with Large Girth
• Contagious sets in expanders
• Diffusion processes on graphs and the averaging principle
• Dynamic approach to k-forcing
• Dynamical Processes on Complex Networks
• Expected values of parameters associated with the minimum rank of a graph
• Extremal values and bounds for the zero forcing number
• Graph bootstrap percolation
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 1943822 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Norm-graphs: Variations and applications
• On a problem of K. Zarankiewicz
• On the structure of linear graphs
• Pseudo-random graphs
• Some bounds on the zero forcing number of a graph
• The history of degenerate (bipartite) extremal graph problems
• The Moore bound for irregular graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Upper bounds on the \(k\)-forcing number of a graph
• Zero forcing sets and the minimum rank of graphs

Cited in

(44)

• The zero forcing polynomial of a graph
• Rigid linkages and partial zero forcing
• Note on forcing problem of trees
• Tight bounds on probabilistic zero forcing on hypercubes and grids
• On the zero forcing number and spectral radius of graphs
• On trees and unicyclic graphs with equal forcing-type numbers
• Probabilistic zero forcing on random graphs
• Zero-forcing in random regular graphs
• Uniform forcing and immune sets in graphs and hypergraphs
• A computational comparison of compact MILP formulations for the zero forcing number
• Multi-color forcing in graphs
• Reconfiguration graphs of zero forcing sets
• Three-state zero forcing on graphs
• Proof of a conjecture on the zero forcing number of a graph
• On Zero Forcing Number of Permutation Graphs
• Edge forcing in butterfly networks
• scientific article; zbMATH DE number 7528059 (Why is no real title available?)
• Constructions of cospectral graphs with different zero forcing numbers
• Propagation time for probabilistic zero forcing
• On the zero forcing number of generalized Sierpiński graphs
• On infection in hypergraphs
• scientific article; zbMATH DE number 6423647 (Why is no real title available?)
• Immune sets in monotone infection rules. Characterization and complexity
• Leaky forcing: a new variation of zero forcing
• Zero forcing density of Archimedean tiling graphs
• The zero forcing number of graphs with the matching number and the cyclomatic number
• Maximum nullity, zero forcing number and propagation time of -path graphs
• Bounding the total forcing number of graphs
• Zero forcing with random sets
• Zero forcing number of some families of graphs
• A unified framework for the expander mixing lemma for irregular graphs and its applications
• The zero forcing number of claw-free cubic graphs
• An approximation algorithm for zero forcing
• Zero forcing number and propagation time discrepancy of some graphs
• Bounds for zero forcing numbers of connected graphs with fixed order and maximum degree
• Zero forcing number and maximum nullity of general power graphs
• On the zero forcing number of complementary prism graphs
• Spreading in claw-free cubic graphs
• Some results on the k-alliance and domination of graphs
• The extremal results for forcing problem of trees
• Spectral bounds for the zero forcing number of a graph
• Clique trees with a given zero forcing number maximizing the A_-spectral radius
• The zero forcing number of expanded paths and cycles
• Zero forcing sets and bipartite circulants

This page was built for publication: The Zero Forcing Number of Graphs

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