The inverse inertia problem for the complements of partial k-trees

DOI10.1016/J.LAA.2013.06.011MaRDI QIDQ2435477zbMATH OpenOpenAlexFDO

Authors Hein van der Holst

Publication date 19 February 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.7004

zbMATH Keywords

treewidthinertiasymmetricgraph complement

Mathematics Subject Classification ID

Trees (05C05) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: Let $mathbbF$ be an infinite field with characteristic different from two. For a graph $G=(V,E)$ with $V=1,\mathrm{...},n$, let $S(G;mathbbF)$ be the set of all symmetric $nimesn$ matrices $A=[a_{i,j}]$ over $mathbbF$ with $a_{i,j}ot=0$, $iot=j$ if and only if $ijinE$. We show that if $G$ is the complement of a partial $k$-tree and $mgeqk+2$, then for all nonsingular symmetric $mimesm$ matrices $K$ over $mathbbF$, there exists an $mimesn$ matrix $U$ such that $U^{T}KUinS(G;mathbbF)$. As a corollary we obtain that, if $k+2leqmleqn$ and $G$ is the complement of a partial $k$-tree, then for any two nonnegative integers $p$ and $q$ with $p+q=m$, there exists a matrix in $S(G;eals)$ with $p$ positive and $q$ negative eigenvalues.

Recommendations

• The minimum semidefinite rank of the complement of partial \(k\)-trees
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• Inertia possibilities for completions of partial hermitian matrices^*
• The inverse eigenvalue and inertia problems for minimum rank two graphs
• On the inertia set of a signed tree with loops

Cites work

• scientific article; zbMATH DE number 2132158 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Graphs whose minimal rank is two
• Graphs whose minimal rank is two: The finite fields case
• Orthogonal representations, minimum rank, and graph complements
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• The minimum rank of symmetric matrices described by a graph: a survey
• The minimum semidefinite rank of the complement of partial \(k\)-trees
• Zero forcing sets and the minimum rank of graphs

Cited in

(3)

• The minimum semidefinite rank of the complement of partial \(k\)-trees
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• On the inertia set of a signed tree with loops

This page was built for publication: The inverse inertia problem for the complements of partial \(k\)-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435477)