Geodesic
Inertia sets for graphs on six or fewer vertices
The electronic journal of linear algebra, Tome 20 (2010), pp. 53-78.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Let G be an undirected graph on n vertices and let $S(G)$ be the set of all real symmetric n $\times n$ matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in $S(G)$, a question which was previously answered when G is a tree. In this paper, a number of new techniques are developed in order to be able to determine possible inertias of general graphs: covers with cliques, covers with cliques and clique-stars, and the graph operations of edge subdivision, edge deletion, joins, and unions. Because most of the associated theorems require additional hypotheses, definitive criteria that apply to all graphs cannot be provided. Nevertheless, these results are strong enough to be able to determine the inertia set of each graph on 6 or fewer vertices and can be applied to many graphs with larger order as well. One consequence of the 1- 6 vertex results is the fact that all of these graphs have balanced inertia. It is also mentioned which of these results guarantee or preserve balanced inertia, and explain how to modify them to include Hermitian matrices.
Classification : 05C05, 05C50, 15A03, 15A57
Keywords: balanced inertia, combinatorial matrix theory, graph, Hermitian, inertia, inverse inertia problem, minimum rank, symmetric 
@article{ELA_2010__20__a50,
     author = {Barrett, Wayne and Jepsen, Camille and Lang, Robert and Mchenry, Emily and Nelson, Curtis and Owens, Kayla},
     title = {Inertia sets for graphs on six or fewer vertices},
     journal = {The electronic journal of linear algebra},
     pages = {53--78},
     publisher = {mathdoc},
     volume = {20},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2010__20__a50/}
}
TY  - JOUR
AU  - Barrett, Wayne
AU  - Jepsen, Camille
AU  - Lang, Robert
AU  - Mchenry, Emily
AU  - Nelson, Curtis
AU  - Owens, Kayla
TI  - Inertia sets for graphs on six or fewer vertices
JO  - The electronic journal of linear algebra
PY  - 2010
SP  - 53
EP  - 78
VL  - 20
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2010__20__a50/
LA  - en
ID  - ELA_2010__20__a50
ER  - 
%0 Journal Article
%A Barrett, Wayne
%A Jepsen, Camille
%A Lang, Robert
%A Mchenry, Emily
%A Nelson, Curtis
%A Owens, Kayla
%T Inertia sets for graphs on six or fewer vertices
%J The electronic journal of linear algebra
%D 2010
%P 53-78
%V 20
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2010__20__a50/
%G en
%F ELA_2010__20__a50
Barrett, Wayne; Jepsen, Camille; Lang, Robert; Mchenry, Emily; Nelson, Curtis; Owens, Kayla. Inertia sets for graphs on six or fewer vertices. The electronic journal of linear algebra, Tome 20 (2010), pp. 53-78. http://geodesic.mathdoc.fr/item/ELA_2010__20__a50/