On the Relationships between Zero Forcing Numbers and Certain Graph Coverings

Fatemeh Alinaghipour Taklimi; Shaun Fallat; Karen Meagher

Special Matrices (2014)

  • Volume: 2, Issue: 1, page 30-45, electronic only
  • ISSN: 2300-7451

Abstract

top
The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing number equals the path cover number.We also give a purely graph theoretical proof that the positive zero forcing number of any outerplanar graphs equals the tree cover number of the graph. These ideas are then extended to the setting of k-trees, where the relationship between the positive zero forcing number and the tree cover number becomes more complex.

How to cite

top

Fatemeh Alinaghipour Taklimi, Shaun Fallat, and Karen Meagher. "On the Relationships between Zero Forcing Numbers and Certain Graph Coverings." Special Matrices 2.1 (2014): 30-45, electronic only. <http://eudml.org/doc/267118>.

@article{FatemehAlinaghipourTaklimi2014,
abstract = {The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing number equals the path cover number.We also give a purely graph theoretical proof that the positive zero forcing number of any outerplanar graphs equals the tree cover number of the graph. These ideas are then extended to the setting of k-trees, where the relationship between the positive zero forcing number and the tree cover number becomes more complex.},
author = {Fatemeh Alinaghipour Taklimi, Shaun Fallat, Karen Meagher},
journal = {Special Matrices},
keywords = {Zero forcing number; positive zero forcing number; path cover number; tree cover number; zero forcing number},
language = {eng},
number = {1},
pages = {30-45, electronic only},
title = {On the Relationships between Zero Forcing Numbers and Certain Graph Coverings},
url = {http://eudml.org/doc/267118},
volume = {2},
year = {2014},
}

TY - JOUR
AU - Fatemeh Alinaghipour Taklimi
AU - Shaun Fallat
AU - Karen Meagher
TI - On the Relationships between Zero Forcing Numbers and Certain Graph Coverings
JO - Special Matrices
PY - 2014
VL - 2
IS - 1
SP - 30
EP - 45, electronic only
AB - The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing number equals the path cover number.We also give a purely graph theoretical proof that the positive zero forcing number of any outerplanar graphs equals the tree cover number of the graph. These ideas are then extended to the setting of k-trees, where the relationship between the positive zero forcing number and the tree cover number becomes more complex.
LA - eng
KW - Zero forcing number; positive zero forcing number; path cover number; tree cover number; zero forcing number
UR - http://eudml.org/doc/267118
ER -

References

top
  1. [1] AIM Minimum Rank - Special Graphs Work Group. Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl., 428/7: 1628-1648, 2008.[WoS] Zbl1135.05035
  2. [2] F. Alinaghipour Taklimi. Zero Forcing Sets for Graphs University of Regina, 2013. Ph.D. thesis. 
  3. [3] E. Almodovar, L. DeLoss, L. Hogben, K. Hogenson, K. Myrphy, T. Peters, C. Ramrez, C. Minimum rank, maximum nullity and zero forcing number, and spreads of these parameters for selected graph families. Involve, 3: 371-392, 2010. Zbl1203.05088
  4. [4] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche, and H. van der Holst. Zero forcing parameters and minimum rank problems. Linear Algebra Appl., 433(2): 401-411, 2010.[WoS] Zbl1209.05139
  5. [5] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche, H. van der Holst. Parameters related to tree-width, zero forcing, and maximum nullity of a graph. J. Graph Theory, 72: 146-177, 2013.[WoS] Zbl1259.05112
  6. [6] F. Barioli, S. Fallat, and L. Hogben. On the difference between the maximum multiplicity and path cover number for treelike graphs. Linear Algebra Appl., 409: 13-31, 2005. Zbl1072.05037
  7. [7] F. Barioli, S. M. Fallat, L. H. Mitchell, and S. K. Narayan. Minimum semideffnite rank of outerplanar graphs and the tree cover number. Electron J. Linear Algebra, 22: 10-21, 2011. Zbl1205.05135
  8. [8] D. Burgarth and V. Giovannetti. Full control by locally induced relaxation. Phys. Rev. Lett., 99(10): 100-501, 2007. 
  9. [9] D. Burgarth and K. Maruyama. Indirect Hamiltonian identiffcation through a small gateway. New J. Physics, 11(10): 103019, 2009. 
  10. [10] D. Burgarth, D. D’Alessandro, L. Hogben, S. Severini, M. Young. Zero forcing, linear and quantum controllability for systems evolving on networks. IEEE Transactions in Automatic Control, 58(9): 2349-2354, 2013. 
  11. [11] R. Diestal. Graph Theory. Graduate Texts in Mathematics, 137, Springer-Verlag, Heidelberg, 2000. 
  12. [12] C. J. Edholm, L. Hogben, M. Huynh, J. Lagrange, D. D. Row. Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph. Linear Algebra Appl., 436: 4352-4372, 2012.[WoS] Zbl1241.05076
  13. [13] J. Ekstrand, C. Erickson, H. T. Hall, D. Hay, L. Hogben, R. Johnson, N. Kingsley, S. Osborne, T. Peters, J. Roat, et al. Positive semideffnite zero forcing. Linear Algebra Appl., 439: 1862-1874, 2013. Zbl1283.05165
  14. [14] J. Ekstrand, C. Erickson, D. Hay, L. Hogben, and J. Roat. Note on positive semideffnite maximum nullity and positive semideffnite zero forcing number of partial 2-trees. Electron J. Linear Algebra, 23: 79-97, 2012. Zbl1252.05118
  15. [15] P. Hackney, B. Harris, M. Lay, L. H. Mitchell, S. K. Narayan, and A. Pascoe. Linearly independent vertices and minimum semideffnite rank. Linear Algebra Appl., 431: 1105 - 1115, 2009.[WoS] Zbl1188.05085
  16. [16] L.-H. Huang, G. J. Chang, H.-G. Yeh. On minimum rank and zero forcing sets of a graph. Linear Algebra Appl., 432: 2961-2973, 2010.[WoS] Zbl1195.05043
  17. [17] AIM Minimum Rank-Special Graphs Work Group. Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl., 428(7): 1628-1648, 2008.[WoS] Zbl1135.05035
  18. [18] C. R. Johnson, R. Loewy, and P. A. Smith. The graphs for which the maximum multiplicity of an eigenvalue is two. Linear Multilinear Algebra, 57(7): 713-736, 2009.[Crossref][WoS] Zbl1225.05167
  19. [19] D. Row. A technique for computing the zero forcing number of a graph with a cut-vertex. Linear Algebra Appl., 436(12): 4423-4432, 2012.[WoS] Zbl1241.05086
  20. [20] D. Row. Zero forcing number, path cover number, and maximum nullity of cacti. Involve, 4(3): 277-291, 2011. Zbl1246.05098
  21. [21] S. Severini. Nondiscriminatory propagation on trees. J. of Phys. A, 41: 482-002 (Fast Track Communication), 2008. Zbl1156.81357
  22. [22] B. Yang. Fast-mixed searching and related problems on graphs. Theoret. Comput. Sci., 507(7): 100-113, 2013 Zbl1302.05197

NotesEmbed ?

top

You must be logged in to post comments.