On the strong Arnol'd hypothesis and the connectivity of graphs

Van Der Holst, Hein

The electronic journal of linear algebra, Tome 20 (2010), pp. 574-585.

Résumé

Summary: In the definition of the graph parameters $\mu (G)$ and $\nu (G)$, introduced by Colin de Verdi` ere, and in the definition of the graph parameter $\xi (G)$, introduced by Barioli, Fallat, and Hogben, a transversality condition is used, called the Strong Arnol'd Hypothesis. In this paper, we define the Strong Arnol'd Hypothesis for linear subspaces L $\subseteq R$ n with respect to a graph G = (V, E), with $V = {1, 2, . . . , n}$. We give a necessary and sufficient condition for a linear subspace L $\subseteq R$ n with dim L $\leq 2$ to satisfy the Strong Arnol'd Hypothesis with respect to a graph G, and we obtain a sufficient condition for a linear subspace L $\subseteq R$ n with dim L = 3 to satisfy the Strong Arnol'd Hypothesis with respect to a graph G. We apply these results to show that if G = (V, E) with $V= {1, 2, . . . , n}$ is a path, 2-connected outerplanar, or 3-connected planar, then each real symmetric n $\times n$ matrix M = [m i,j ] with m i,j 0 if ij $\in E$ and m i,j = 0 if i = j and ij $\in E$ (and no restriction on the diagonal), having exactly one negative eigenvalue, satisfies the Strong Arnol'd Hypothesis.

Détail

Classification : 05C50, 15A18
Keywords: symmetric matrices, nullity, graphs, transversality, planar, outerplanar, graph minor