On the minimum semidefinite rank of a simple graph. (English) Zbl 1223.05170
Summary: The minimum semidefinite rank (msr) of a graph is defined to be the minimum rank among all positive semidefinite matrices whose zero/nonzero pattern corresponds to that graph. We recall some known facts and present new results, including results concerning the effects of vertex or edge removal from a graph on msr.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 15B57 | Hermitian, skew-Hermitian, and related matrices |
References:
| [1] | DOI: 10.1016/j.laa.2006.05.020 · Zbl 1112.05061 · doi:10.1016/j.laa.2006.05.020 |
| [2] | DOI: 10.1016/j.laa.2004.06.019 · Zbl 1052.05045 · doi:10.1016/j.laa.2004.06.019 |
| [3] | Barrett W, J. Linear Algebra 11 pp 258– (2004) |
| [4] | DOI: 10.1137/050629793 · Zbl 1226.05151 · doi:10.1137/050629793 |
| [5] | DOI: 10.1016/j.laa.2006.02.018 · Zbl 1106.05059 · doi:10.1016/j.laa.2006.02.018 |
| [6] | DOI: 10.1016/0095-8956(86)90028-6 · Zbl 0603.05023 · doi:10.1016/0095-8956(86)90028-6 |
| [7] | DOI: 10.1016/j.laa.2007.05.036 · Zbl 1122.05057 · doi:10.1016/j.laa.2007.05.036 |
| [8] | DOI: 10.1016/j.laa.2007.12.004 · Zbl 1147.05049 · doi:10.1016/j.laa.2007.12.004 |
| [9] | Horn RA, Matrix Analysis (1990) |
| [10] | DOI: 10.1016/j.laa.2007.10.031 · Zbl 1135.05037 · doi:10.1016/j.laa.2007.10.031 |
| [11] | DOI: 10.1016/S0024-3795(98)10007-1 · Zbl 0946.15001 · doi:10.1016/S0024-3795(98)10007-1 |
| [12] | DOI: 10.1016/j.disc.2005.04.025 · Zbl 1114.05061 · doi:10.1016/j.disc.2005.04.025 |
| [13] | DOI: 10.1080/03081089508818377 · Zbl 0832.05081 · doi:10.1080/03081089508818377 |
| [14] | DOI: 10.1016/0024-3795(95)00238-3 · Zbl 0864.05069 · doi:10.1016/0024-3795(95)00238-3 |
| [15] | DOI: 10.1137/S0895479802410293 · Zbl 1055.05073 · doi:10.1137/S0895479802410293 |
| [16] | DOI: 10.1016/S0024-3795(03)00642-6 · Zbl 1029.05099 · doi:10.1016/S0024-3795(03)00642-6 |
| [17] | West DB, Introduction to Graph Theory (1996) |
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.
