×

On graphs maximizing the zero forcing number. (English) Zbl 1512.05231

Summary: A subset \(Z\) of vertex set \(V (G)\) of a graph \(G\) is a zero forcing set of \(G\) if iteratively adding vertices to \(Z\) from \(V (G) \setminus Z\) that are the unique neighbor in \(V (G) \setminus Z\) of some vertex in \(Z\), results in the entire \(V (G)\) of \(G\). The zero forcing number \(Z (G)\) of \(G\) is the minimum cardinality of a zero forcing set of \(G\). In a recent work, Y. Caro and R. Pepper [Theory Appl. Graphs 2, No. 2, Article 2, 5 p. (2015; Zbl 1416.05265)] proved that \(Z (G) \leq \frac{(\Delta - 2) n - (\Delta - \delta) + 2}{\Delta - 1}\), where \(n\), \(\Delta\), \(\delta\) are the order, maximum degree, minimum degree of \(G\), respectively. In this paper we completely characterize extremal graphs attained the upper bound, solving a problem proposed by L. Lu et al. [Discrete Appl. Math. 213, 233–237 (2016; Zbl 1344.05063)]. Our result further generalizes the characterization of extremal regular graphs obtained by M. Gentner and D. Rautenbach [ibid. 236, 203–213 (2018; Zbl 1377.05058)] and Lu et al. [loc. cit.].

MSC:

05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aazami, A., Hardness Results and Approximation Algorithms for Some Problems on Graphs (2008), University of Waterloo, (Ph.D. thesis)
[2] Amos, D.; Caro, Y.; Davila, R.; Pepper, R., Upper bounds on the \(k\)-forcing number of a graph, Discrete Appl. Math., 181, 1-10 (2015) · Zbl 1304.05041
[3] Barioli, F.; Barrett, W.; Butler, S.; Cioabǎ, S. M.; Cvetković, D.; Fallat, S. M.; Godsil, C.; Haemers, W.; Hogben, L.; Mikkelson, R.; Narayan, S.; Pryporova, O.; Sciriha, I.; So, W.; Stevanović, D.; van der Holst, H.; Vander Meulen, K.; Wangsness, A., Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428, 1628-1648 (2008) · Zbl 1135.05035
[4] Barioli, F.; Barrett, W.; Fallat, S. M.; Hall, H. T.; Hogben, L.; Shader, B.; van den Driessche, P.; van der Holst, H., Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory, 72, 2, 146-177 (2013) · Zbl 1259.05112
[5] Burgarth, D.; Giovannetti, V., Full control by locally induced relaxation, Phys. Rev. Lett., 99, 100-501 (2007)
[6] Burgarth, D.; Giovannetti, V.; Hogben, L.; Severini, S.; Young, M., Logic circuits from zero forcing, Nat. Comput., 14, 485-490 (2015) · Zbl 1416.94079
[7] Caro, Y.; Pepper, R., Dynamic approach to \(k\)-forcing, Theory Appl. Graphs, 2, 2, 2 (2015) · Zbl 1416.05265
[8] Chekuri, C.; Korula, N., A graph reduction step preserving element-connectivity and applications, (Automata, Languages and Programming (2009), Springer), 254-265 · Zbl 1247.05236
[9] Davila, R.; Henning, M. A., The forcing number of graphs with given girth, Quaest. Math., 41, 1-16 (2017)
[10] Davila, R.; Kalinowski, T.; Stephen, S., A lower bound on the zero forcing number, Discrete Appl. Math., 250, 363-367 (2018) · Zbl 1398.05083
[11] Davila, R.; Kenter, F., Bounds for the zero forcing number of graphs with large girth, Theory Appl. Graph., 2, 2, 1 (2015) · Zbl 1416.05169
[12] Fallat, S. M.; Meagher, K.; Yang, B., On the complexity of the positive semidefinite zero forcing number, Linear Algebra Appl., 491, 101-122 (2016) · Zbl 1330.05064
[13] Ferrero, D.; Hogben, L.; Kenter, F.; Young, M., The relationship between \(k\)-forcing and \(k\)-power domination, Discrete Math., 341, 1789-1797 (2018) · Zbl 1384.05122
[14] Gentner, M.; Penso, L. D.; Rautenbach, D.; Souza, U. S., Extremal values and bounds for the zero forcing number, Discrete Appl. Math., 213, 196-200 (2016) · Zbl 1346.05068
[15] Gentner, M.; Rautenbach, D., Some bounds on the zero forcing number of a graph, Discrete Appl. Math., 236, 203-213 (2018) · Zbl 1377.05058
[16] Li, S.; Sun, W., On the zero forcing number of a graph involving some classical parameters, J. Comb. Optim., 39, 365-384 (2020) · Zbl 1434.05113
[17] Lu, L.; Wu, B.; Tang, Z., Proof of a conjecture on the zero forcing number of a graph, Discrete Appl. Math., 213, 223-237 (2016) · Zbl 1344.05063
[18] Row, D. D., A technique for computing the forcing number of a graph with a cut-vertex, Linear Algebra Appl., 436, 4423-4432 (2012) · Zbl 1241.05086
[19] Wang, X.; Wong, D.; Zhang, Y., Zero forcing number of a graph in terms of the number of pendant vertices, Linear Multilinear Algebra, 68, 1424-1433 (2020) · Zbl 1459.05248
[20] Yang, B., Fast-mixed searching and related problems on graphs, Theoret. Comput. Sci., 507, 7, 100-113 (2013) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.