Throttling for zero forcing and variants

zbMATH Open1437.05070arXiv1807.07030MaRDI QIDQ5206911FDOQ5206911

Authors: Joshua Carlson 

Publication date: 19 December 2019

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.

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

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

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)

Cites Work

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

Cited In (16)

• Blocking zero forcing processes in Cartesian products of graphs
• Leaky forcing: a new variation of zero forcing
• Properties of a \(q\)-analogue 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
• Throttling for standard zero forcing on directed graphs
• Product throttling
• Power domination throttling
• Title not available (Why is that?)
• The \(q\)-analogue of zero forcing for certain families of graphs
• Various characterizations of throttling numbers

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)