Computing inertia sets using atoms. (English) Zbl 1241.05065
Summary: We consider the problem of computing inertia sets for graphs. By using tools for combining the inertia sets of smaller graphs we can reduce this problem to understanding the inertia sets for three-connected graphs that are not joins. We term such graphs atoms and give the inertia sets for all atoms on at most seven vertices. This can be used to compute the inertia sets for all graphs on at most seven vertices.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A99 | Basic linear algebra |
| 15A03 | Vector spaces, linear dependence, rank, lineability |
References:
| [1] | Barioli, F.; Fallat, S., On the minimum rank of the join of graphs and decomposable graphs, Linear Algebra Appl., 421, 252-263 (2007) · Zbl 1112.05061 |
| [2] | Barioli, F.; Fallat, S.; Hogben, L., Computation of minimal rank and path cover number for certain graphs, Linear Algebra Appl., 392, 289-303 (2004) · Zbl 1052.05045 |
| [3] | Barioli, F.; Fallat, S.; Hogben, L., A Variant on the Graph Parameters of Colin De VerdiÈre: Implications to the Minimum Rank of Graphs, Electron. J. Linear Algebra, 13, 387-404 (2005) · Zbl 1092.05042 |
| [4] | Wayne Barrett, H. Tracy Hall, Hein van der Holst, The inertia set of the join of graphs, preprint.; Wayne Barrett, H. Tracy Hall, Hein van der Holst, The inertia set of the join of graphs, preprint. |
| [5] | Barrett, Wayne; Tracy Hall, H.; Loewy, Raphael, The inverse inertia problem for graphs: cut vertices, trees and a counterexample, Linear Algebra Appl., 431, 1147-1191 (2009) · Zbl 1175.05032 |
| [6] | Barrett, Wayne; van der Holst, Hein; Loewy, Raphael, Graphs whose minimal rank is two, Electron. J. Linear Algebra, 11, 258-280 (2004) · Zbl 1070.05059 |
| [7] | Barrett, Wayne; Jepsen, Camille; Lang, Robert; McHenry, Emily; Nelson, Curtis; Owens, Kayla, Inertia sets for graphs on six or fewer vertices, Electron. J. Linear Algebra, 20, 53-78 (2010) · Zbl 1189.05048 |
| [8] | de Verdière, Yves Colin, Multiplicities of eigenvalues and tree-width of graphs, J. Combin. Theory Ser. B, 74, 121-146 (1998) · Zbl 1027.05064 |
| [9] | Diestel, Reinhard, Graph Theory. Graph Theory, third ed. (2000), Springer: Springer New York · Zbl 0945.05002 |
| [10] | Fallat, Shaun; Hogben, Leslie, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl., 426, 558-582 (2007) · Zbl 1122.05057 |
| [11] | van der Holst, Hein, Graphs with magnetic Schrödinger operators of low corank, J. Combin. Theory Ser. B, 84, 311-339 (2002) · Zbl 1024.05060 |
| [12] | van der Holst, Hein, Some connectivity properties for excluded minors of the graph invariant \(\nu(G)\), European J. Combin., 24, 929-946 (2003) · Zbl 1026.05080 |
| [13] | van der Holst, Hein, Three-connected graphs whose maximum nullity is at most three, Linear Algebra Appl., 429, 625-632 (2008) · Zbl 1145.05037 |
| [14] | van der Holst, Hein; Lovász, László; Shrijver, Alexander, The Colin de Verdière graph parameter, (Graph Theory and Combinatorial Biology (Balatonlelle, 1996). Graph Theory and Combinatorial Biology (Balatonlelle, 1996), Bolya Soc. Math. Stud., vol. 7 (1999), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 29-85 · Zbl 0930.05065 |
| [15] | Hein van der Holst, personal communication.; Hein van der Holst, personal communication. |
| [16] | van der Holst, Hein, The maximum corank of graphs with a 2-separation, Linear Algebra Appl., 428, 1587-1600 (2008) · Zbl 1135.05040 |
| [17] | Mark C. Kempton, The Minimum Rank, Inverse Inertia, and Inverse Eigenvalue Problems for Graphs, Masters thesis, Brigham Young University, 2010. Available from: <; Mark C. Kempton, The Minimum Rank, Inverse Inertia, and Inverse Eigenvalue Problems for Graphs, Masters thesis, Brigham Young University, 2010. Available from: < |
| [18] | Merris, Russell, Graph Theory (2001), John Wiley & Sons: John Wiley & Sons New York · Zbl 0963.05001 |
| [19] | Read, Ronald C.; Wilson, Robin J., An Atlas of Graphs (1998), Oxford University Press: Oxford University Press New York · Zbl 0908.05001 |
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.
