×

The zero forcing polynomial of a graph. (English) Zbl 1408.05072

Let \(G\) be a graph. If \(S \subseteq V(G)\) is a set of initially colored vertices, then the zero forcing color change rule demands that at each timestep, a colored vertex \(u\) with a single uncolored neighbor \(v\) forces that neighbor to become colored. The closure of \(S\) is the set of colored vertices obtained after the color change rule is applied in timesteps until no new vertex can be forced in a timestep. A zero forcing set is a set whose closure is all \(V\). In the present paper, the authors introduce the zero forcing polynomial of a graph.
Definition. Let \(G\) be a graph on \(n\) vertices and \(z(G;i)\) be the number of zero forcing sets of \(G\) with cardinality \(i\). The zero forcing polynomial of \(G\) is defined as \[ \mathcal{Z}(G;x) = \sum_{i=1}^n z(G;i)x^i. \] Obviously, the defined polynomial is related to the zero forcing number of \(G\), denoted by \(Z(G)\), which is defined as the minimum cardinality of a zero forcing set.
In the paper, the extremal coefficients of the zero forcing polynomial are firstly studied in Section 3. In the following section, the polynomial is investigated for some specific families of graphs, for example complete graphs, paths, cycles, wheels, and threshold graphs. Finally, in Section 5, various structural properties of the zero forcing polynomial are examined (such as multiplicativity, unimodality, uniqueness). In addition, several families of graphs which can be recognized by their zero forcing polynomials are identified. However, it does not hold in general that if \(\mathcal{Z}(G;x) = \mathcal{Z}(H;x)\), then \(G \backsimeq H\). In the conclusion, some interesting open problems are also presented. Among them, the following question is included: for any graph \(G\) on \(n\) vertices, is it true that \(z(G;i) \leq z(P_n;i)\), for \(1 \leq i \leq n\)?

MSC:

05C31 Graph polynomials
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] AIM Minimum Rank Catalog. Available at: http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/; AIM Minimum Rank Catalog. Available at: http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/
[2] AIM Special Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428, 7, 1628-1648 (2008)
[3] Akbari, S.; Alikhani, S.; Peng, Y.-H., Characterization of graphs using domination polynomials, European J. Combin., 31, 7, 1714-1724 (2010) · Zbl 1207.05092
[4] Akbari, S.; Oboudi, M. R., On the edge cover polynomial of a graph, European J. Combin., 34, 2, 297-321 (2013) · Zbl 1254.05077
[5] Alikhani, S.; Peng, Y.-H., Introduction to domination polynomial of a graph, Ars Combin., 114, 257-266 (2014) · Zbl 1324.05138
[6] 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
[7] Barioli, F.; Barrett, W.; Fallat, S. M.; Hall, H. T.; Hogben, L.; Shader, B.; Van Den Driessche, P.; Van Der Holst, H., Zero forcing parameters and minimum rank problems, Linear Algebra Appl., 433, 2, 401-411 (2010) · Zbl 1209.05139
[8] Berliner, A.; Bozeman, C.; Butler, S.; Catral, M.; Hogben, L.; Kroschel, B.; Lin, J. C.-H.; Warnberg, N.; Young, M., Zero forcing propagation time on oriented graphs, Discrete Appl. Math. (2017) · Zbl 1361.05041
[9] Birkhoff, G. D., A determinant formula for the number of ways of coloring a map, Ann. Mat., 14, 1/4, 42-46 (1912) · JFM 43.0574.02
[10] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications, volume 290 (1976), Macmillan: Macmillan London · Zbl 1226.05083
[11] Bozeman, C.; Brimkov, B.; Erickson, C.; Ferrero, D.; Flagg, M.; Hogben, L., Restricted power domination and zero forcing problems, J. Comb. Optim. (2018), in press
[12] Brimkov, B., Graph Coloring, Zero Forcing, and Related Problems (2017), Rice University
[13] Brimkov, B.; Fast, C. C.; Hicks, I. V., Computational approaches for zero forcing and related problems, European J. Oper. Res. (2018), in press
[14] Brimkov, B.; Hicks, I. V., Complexity and computation of connected zero forcing, Discrete Appl. Math., 229, 31-45 (2017) · Zbl 1367.05115
[15] Brown, J. I.; Tufts, J., On the roots of domination polynomials, Graphs Combin., 30, 3, 527-547 (2014) · Zbl 1292.05205
[16] Brylawski, T. H., A decomposition for combinatorial geometries, Trans. Amer. Math. Soc., 171, 235-282 (1972) · Zbl 0224.05007
[17] Burgarth, D.; D’Alessandro, D.; Hogben, L.; Severini, S.; Young. Zero forcing, M., linear and quantum controllability for systems evolving on networks, IEEE Trans. Automat. Control, 58, 9, 2349-2354 (2013) · Zbl 1369.93079
[18] Burgarth, D.; Giovannetti, V., Full control by locally induced relaxation, Phys. Rev. Lett., 99, 10, Article 100501 pp. (2007)
[19] Burgarth, D.; Giovannetti, V.; Hogben, L.; Severini, S.; Young, M., Logic circuits from zero forcing, Nat. Comput., 14, 3, 485-490 (2015) · Zbl 1416.94079
[20] Butler, S.; Grout, J.; Hall, H. T., Using variants of zero forcing to bound the inertia set of a graph, Electron. J. Linear Algebra, 30, 1, 1 (2015) · Zbl 1323.05088
[21] Butler, S.; Young, M., Throttling zero forcing propagation speed on graphs, Australas. J. Combin., 57, 65-71 (2013) · Zbl 1293.05220
[22] Carlson, J.; Hogben, L.; Kritschgau, J.; Lorenzen, K.; Ross, M. S.; Selken, S.; Martinez, V. V., Throttling positive semidefinite zero forcing propagation time on graphs, Discrete Appl. Math. (2018), in press · Zbl 1404.05050
[23] Caro, Y.; Pepper, R., Dynamic approach to \(k\)-forcing, Theory Appl. Graphs, 2, 2 (2015) · Zbl 1416.05265
[24] Chari, M.; Colbourn, C. J., Reliability polynomials: a survey, J. Comb. Inf. Syst. Sci., 22, 3-4, 177-193 (1997) · Zbl 0924.05065
[25] Chvátal, V.; Hammer, P. L., Aggregation of inequalities in integer programming, Ann. Discret. Math., 1, 145-162 (1977)
[26] Deepak, G.; Soner, N., Connected domination polynomial of a graph, Int. J. Math. Arch., 4, 11, 90-96 (2014)
[27] Dong, F. M.; Hendy, M. D.; Teo, K. L.; Little, C. H., The vertex-cover polynomial of a graph, Discrete Math., 250, 1-3, 71-78 (2002) · Zbl 1007.05079
[28] Dreyer, P. A.; Roberts, F. S., Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math., 157, 7, 1615-1627 (2009) · Zbl 1163.92035
[29] Ekstrand, J.; Erickson, C.; Hall, H. T.; Hay, D.; Hogben, L.; Johnson, R.; Kingsley, N.; Osborne, S.; Peters, T.; Roat, J., Positive semidefinite zero forcing, Linear Algebra Appl., 439, 7, 1862-1874 (2013) · Zbl 1283.05165
[30] Ellis-Monaghan, J. A.; Merino, C., Graph polynomials and their applications I: The Tutte polynomial, (Structural Analysis of Complex Networks (2011), Springer), 219-255 · Zbl 1221.05002
[31] Ellis-Monaghan, J. A.; Merino, C., Graph polynomials and their applications II: Interrelations and interpretations, (Structural Analysis of Complex Networks (2011), Springer), 257-292 · Zbl 1221.05003
[32] Fast, C. C., Novel Techniques for the Zero-Forcing and p-Median Graph Location Problems (2017), Rice University
[33] Goldberg, F.; Berman, A., Zero forcing for sign patterns, Linear Algebra Appl., 447, 56-67 (2014) · Zbl 1288.05156
[34] Hajiabolhassan, H.; Mehrabadi, M., On clique polynomials, Australas. J. Combin., 18, 313-316 (1998) · Zbl 0920.05067
[35] Haynes, T. W.; Hedetniemi, S. M.; Hedetniemi, S. T.; Henning, M. A., Domination in graphs applied to electric power networks, SIAM J. Discrete Math., 15, 4, 519-529 (2002) · Zbl 1006.05043
[36] Hoede, C.; Li, X., Clique polynomials and independent set polynomials of graphs, Discrete Math., 125, 1-3, 219-228 (1994) · Zbl 0799.05030
[37] Hogben, L.; Kingsley, N.; Meyer, S.; Walker, S.; Young, M., Propagation time for zero forcing on a graph, Discrete Appl. Math., 160, 13, 1994-2005 (2012) · Zbl 1246.05056
[38] Hogben, L.; Palmowski, K. F.; Roberson, D. E.; Young, M., Fractional zero forcing via three-color forcing games, Discrete Appl. Math., 213, 114-129 (2016) · Zbl 1344.05062
[39] Jahari, S.; Alikhani, S., Domination polynomials of \(k\)-tree related graphs, Int. J. Comb., 2014 (2014)
[40] Johnson, C. R.; Loewy, R.; Smith, P. A., The graphs for which the maximum multiplicity of an eigenvalue is two, Linear Multilinear Algebra, 57, 7, 713-736 (2009) · Zbl 1225.05167
[41] Jones, V. F., A polynomial invariant for knots via von Neumann algebras, Bull. Amer. Math. Soc., 12, 103-111 (1985) · Zbl 0564.57006
[42] Kotek, T.; Preen, J.; Simon, F.; Tittmann, P.; Trinks, M., Recurrence relations and splitting formulas for the domination polynomial, Electron. J. Combin., 19 (2012) · Zbl 1252.05164
[43] Row, D. D., A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl., 436, 12, 4423-4432 (2012) · Zbl 1241.05086
[44] Stanley, R. P., Acyclic orientations of graphs, (Classic Papers in Combinatorics (1987), Springer), 453-460
[45] Tutte, W. T., On dichromatic polynomials, J. Combin. Theory, 2, 3, 301-320 (1967) · Zbl 0147.42902
[46] Warnberg, N., Positive semidefinite propagation time, Discrete Appl. Math., 198, 274-290 (2016) · Zbl 1327.05128
[47] Whitney, H., A logical expansion in mathematics, Bull. Amer. Math. Soc., 38, 8, 572-579 (1932) · JFM 58.0605.08
[48] Yang, B., Fast-mixed searching and related problems on graphs, Theoret. Comput. Sci., 507, 100-113 (2013) · Zbl 1302.05197
[49] Zhao, M.; Kang, L.; Chang, G. J., Power domination in graphs, Discrete Math., 306, 15, 1812-1816 (2006) · Zbl 1099.05065
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.