Throttling for zero forcing and variants

MaRDI QIDQ5206911zbMATH OpenFDO

Authors Joshua Carlson

Publication date 19 December 2019

Full work available at URL https://arxiv.org/abs/1807.07030, http://ajc.maths.uq.edu.au/pdf/75/ajc_v75_p096.pdf

zbMATH Keywords

extreme throttling numbers

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Zero forcing is a process on a graph in which the goal is to force all vertices to become blue by applying a color change rule. Throttling minimizes the sum of the number of vertices that are initially blue and the number of time steps needed to color every vertex. We introduce a new universal definition of throttling for variants of zero forcing and the study of throttling for the minor monotone floor of zero forcing. We introduce the technique of using a zero forcing process to extend a given graph. For standard zero forcing and its floor, we use these extensions to characterize graphs with throttling number $leqt$ as certain minors of Cartesian products of complete graphs and paths. We apply these characterizations to determine graphs with extreme throttling numbers.

Recommendations

• Various characterizations of throttling numbers
• Throttling positive semidefinite zero forcing propagation time on graphs
• Skew throttling
• Throttling for standard zero forcing on directed graphs
• Throttling zero forcing propagation speed on graphs

Cites work

• A protocol for cooling and controlling composite systems by local interactions
• Fast-mixed searching and related problems on graphs
• Mixed searching and proper-path-width
• Multiplicities of eigenvalues and tree-width of graphs
• Nondiscriminatory propagation on trees
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Power domination throttling
• Propagation time for zero forcing on a graph
• Throttling positive semidefinite zero forcing propagation time on graphs
• Throttling zero forcing propagation speed on graphs
• Zero forcing sets and the minimum rank of graphs

Cited in

(16)

• Blocking zero forcing processes in Cartesian products of graphs
• Properties of a \(q\)-analogue of zero forcing
• Leaky forcing: a new variation of zero forcing
• On leaky forcing and resilience
• A note on variants of zero forcing
• Fuzzification of Zero Forcing Process
• Skew throttling
• Fractional zero forcing via three-color forcing games
• Throttling zero forcing propagation speed on graphs
• Throttling processes equivalent to full throttling on trees
• Product throttling
• Throttling for standard zero forcing on directed graphs
• Power domination throttling
• scientific article; zbMATH DE number 7731182 (Why is no real title available?)
• Various characterizations of throttling numbers
• The \(q\)-analogue of zero forcing for certain families of graphs

This page was built for publication: Throttling for zero forcing and variants

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