×

Parameters related to tree-width, zero forcing, and maximum nullity of a graph. (English) Zbl 1259.05112

Summary: Tree-width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph.
We establish relationships between these parameters, including several Colin de Verdière type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree-width, largeur d’arborescence, path-width, and proper path-width are each characterized in terms of a minor monotone floor of a certain zero forcing parameter defined by a color change rule.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C83 Graph minors
15A03 Vector spaces, linear dependence, rank, lineability
15A18 Eigenvalues, singular values, and eigenvectors
05C40 Connectivity
05C75 Structural characterization of families of graphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] http://aimath.org/pastworkshops/ma trixspectrum.html
[2] Barioli, Zero forcing sets and the minimum rank of graphs, Linear Algebr Appl 428/7 pp 1628– (2008)
[3] Barioli, Zero forcing parameters and minimum rank problems, Linear Algebr Appl 433 pp 401– (2010) · Zbl 1209.05139 · doi:10.1016/j.laa.2010.03.008
[4] Barioli, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron J Linear Algebra 18 pp 126– (2009) · Zbl 1169.05345
[5] Barioli, Computation of minimal rank and path cover number for graphs, Linear Algebr Appl 392 pp 289– (2004) · Zbl 1052.05045 · doi:10.1016/j.laa.2004.06.019
[6] Barioli, A variant on the graph parameters of Colin de Verdière: Implications to the minimum rank of graphs, Electron J Linear Algebra 13 pp 387– (2005) · Zbl 1092.05042
[7] Berman, An upper bound for the minimum rank of a graph, Linear Algebra and its Applications 429/7 pp 1629– (2008) · Zbl 1144.05314 · doi:10.1016/j.laa.2008.04.038
[8] Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theor Comput Sci 209 pp 1– (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4
[9] Bokal, The minor crossing number, SIAM J Discrete Math 20 pp 344– (2006) · Zbl 1118.05016 · doi:10.1137/05062706X
[10] Booth, On the minimum rank among positive semidefinite matrices with a given graph, SIAM J Matrix Anal Appl 30 pp 731– (2008) · Zbl 1226.05151 · doi:10.1137/050629793
[11] Borie, Handbook of Graph Theory pp 99– (2004)
[12] Burgarth, Full control by locally induced relaxation, Phys Rev Lett 99 pp 100501– (2007) · doi:10.1103/PhysRevLett.99.100501
[13] S. Butler L. DeLoss J. Grout H. T. Hall J. LaGrange T. McKay J. Smith G. Tims Minimum Rank Library ( Sage programs for calculating bounds on the minimum rank of a graph, and for computing zero forcing parameters) http://sage.cs.drake.edu/home/pub/67/ jason.grout@drake.edu
[14] Colin de Verdière, Graph Structure Theory pp 137– (1993) · doi:10.1090/conm/147/01168
[15] Colin de Verdière, Multiplicities of eigenvalues and tree-width of graphs, J Combin Theory B 74 pp 121– (1998) · Zbl 1027.05064 · doi:10.1006/jctb.1998.1834
[16] R. Diestel Graph Theory Electronic Edition Springer-Verlag NY 2000
[17] Fallat, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebr Appl 426 pp 558– (2007) · Zbl 1122.05057 · doi:10.1016/j.laa.2007.05.036
[18] Fijavž, Minimum degree and graph minors, Electron Notes Discrete Math 31 pp 79– (2008) · Zbl 1267.05241 · doi:10.1016/j.endm.2008.06.013
[19] Hackney, Linearly independent vertices and minimum semidefinite rank, Linear Algebr Appl 431 pp 1105– (2009) · Zbl 1188.05085 · doi:10.1016/j.laa.2009.03.030
[20] Hogben, Forbidden minors for the class of graphs G with {\(\xi\)}(G), Linear Algebr Appl 423 pp 42– (2007) · Zbl 1118.05064 · doi:10.1016/j.laa.2006.08.003
[21] Johnson, The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra 46 pp 139– (1999) · Zbl 0929.15005 · doi:10.1080/03081089908818608
[22] Johnson, The graphs for which maximum multiplicity of an eigenvalue is two, Linear Multilinear Algebra 57 pp 713– (2009) · Zbl 1225.05167 · doi:10.1080/01445340802354580
[23] Kotlov, Note: Spectral characterization of tree-width-two graphs, Combinatorica 20 pp 147– (2000) · Zbl 0980.05043 · doi:10.1007/s004930070038
[24] LaPaugh, Recontamination does not help to search a graph, J Assoc Comput Mach 40 (2) pp 224– (1993) · Zbl 0768.68048 · doi:10.1145/151261.151263
[25] Lovász, Orthogonal representations and connectivity of graphs, Linear Algebr Appl 114/115 pp 439– (1989) · Zbl 0681.05048 · doi:10.1016/0024-3795(89)90475-8
[26] Lovász, A correction: ”Orthogonal representations and connectivity of graphs, Linear Algebr Appl 313 pp 101– (2000) · Zbl 0954.05032 · doi:10.1016/S0024-3795(00)00091-4
[27] Mader, Homomorphiesätze für Graphen, Math Ann 178 pp 154– (1968) · Zbl 0165.57401 · doi:10.1007/BF01350657
[28] Nylen, Minimum-rank matrices with prescribed graph, Linear Algebr Appl 248 pp 303– (1996) · Zbl 0864.05069 · doi:10.1016/0024-3795(95)00238-3
[29] Seymour, Graph searching and a min-max theorem for tree-width, J Comb Theory B 58 pp 22– (1993) · Zbl 0795.05110 · doi:10.1006/jctb.1993.1027
[30] Severini, Nondiscriminatory propagation on trees, J Phys A 41 pp 482– (2008) · Zbl 1156.81357 · doi:10.1088/1751-8113/41/48/482002
[31] Takahashi, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete Math 127 pp 293– (1994) · Zbl 0795.05123 · doi:10.1016/0012-365X(94)90092-2
[32] Takahashi, Mixed searching and proper-path-width, Theor Comput Sci 137 pp 253– (1995) · Zbl 0873.68148 · doi:10.1016/0304-3975(94)00160-K
[33] van der Holst, On the ”Largeur d’Arborescence, J Graph Theory 41 pp 24– (2002) · Zbl 0996.05034 · doi:10.1002/jgt.10046
[34] van der Holst, Graphs whose positive semi-definite matrices have nullity at most two, Linear Algebr Appl 375 pp 1– (2003) · Zbl 1029.05099 · doi:10.1016/S0024-3795(03)00642-6
[35] van der Holst, Three-connected graphs whose maximum nullity is at most three, Linear Algebra and its Applications 429 pp 625– (2007) · Zbl 1145.05037 · doi:10.1016/j.laa.2008.03.018
[36] H. van der Holst L. Lovász A. Schrijver Graph Theory and Computational Biology János Bolyai Math. Soc Budapest 1999 29 85
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.