×

zbMATH — the first resource for mathematics

Throttling for zero forcing and variants. (English) Zbl 1437.05070
Author’s 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. This paper provides a new general definition of throttling for variants of zero forcing and studies throttling for the minor monotone floor of zero forcing. The technique of using a zero forcing process to extend a given graph is introduced. For standard zero forcing and its floor, these extensions are used to characterize graphs with throttling number at most \(t\) as certain minors of Cartesian products of complete graphs and paths. Finally, these characterizations are applied to determine graphs with extreme throttling numbers.
MSC:
05C15 Coloring of graphs and hypergraphs
05C76 Graph operations (line graphs, products, etc.)
05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: Link arXiv
References:
[1] AIM Minimum Rank—Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. M. Cioab˘a, D. Cvetkovi´c, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovi´c, H. van der Holst, K. Vander Meulen, A. Wangsness), Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), 1628- 1648. · Zbl 1135.05035
[2] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory 72 (2013), 146-177. · Zbl 1259.05112
[3] B. Brimkov, J. Carlson, I. V. Hicks, R. Patel and L. Smith, Power domination throttling, Theoret. Comput. Sci. (in press); https://doi.org/10.1016/j.tcs.2019.06.008. · Zbl 1431.68044
[4] D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett. 99 (2007), 100501. · Zbl 1166.81307
[5] S. Butler and M. Young, Throttling zero forcing propagation speed on graphs, Australas. J. Combin. 57 (2013), 65-71. · Zbl 1293.05220
[6] J. Carlson, L. Hogben, J. Kritschgau, K. Lorenzen, M. S. Ross, S. Selken and V. Valle Martinez, Throttling positive semidefinite zero forcing propagation time on graphs, Discrete Appl. Math. 254 (2019), 33-46. · Zbl 1404.05050
[7] Y. Colin de Verdi‘ere, Multiplicities of eigenvalues and tree-width of graphs, J. Combin. Theory Ser. B 74 (1998), 121-146.
[8] L. Hogben, M. Huynh, N. Kingsley, S. Meyer, S. Walker and M. Young, Propagation time for zero forcing on a graph, Discrete Appl. Math. 160 (2012), 1994- 2005. · Zbl 1246.05056
[9] S. Severini, Nondiscriminatory propagation on trees, J. Physics A. 41 (2008), 482-002. · Zbl 1156.81357
[10] A. Takahashi, S. Ueno and Y. Kajitani, Mixed searching and proper-path-width, Theoret. Comput. Sci. 137 (1995), 253-268. · Zbl 0873.68148
[11] B. Yang, Fast-mixed searching and related problems on graphs, Theoret. Comput. Sci. 507 (2013), 100-113. · Zbl 1302.05197
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.