The Gram dimension of a graph

DOI10.1007/978-3-642-32147-4_32MaRDI QIDQ3167639zbMATH OpenOpenAlexFDO

Authors A. Varvitsiotis, Monique Laurent

Publication date 2 November 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph minors (05C83) Analysis of algorithms and problem complexity (68Q25)

Abstract: The Gram dimension $gd(G)$ of a graph is the smallest integer $kge1$ such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment of unit vectors lying in $o{R}^k$, having the same inner products on the edges of the graph. The class of graphs satisfying $gd(G)lek$ is minor closed for fixed $k$, so it can characterized by a finite list of forbidden minors. For $kle3$, the only forbidden minor is $K_{k+1}$. We show that a graph has Gram dimension at most 4 if and only if it does not have $K_5$ and $K_{2,2,2}$ as minors. We also show some close connections to the notion of $d$-realizability of graphs. In particular, our result implies the characterization of 3-realizable graphs of Belk and Connelly cite{Belk,BC}.

Recommendations

• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Realizability of graphs
• Realizability of graphs in three dimensions
• The dimension of a graph
• On a minor-monotone graph invariant

Cited in

(10)

• Maximum likelihood threshold and generic completion rank of graphs
• The lattice dimension of a graph
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Iterative universal rigidity
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• Complexity of the positive semidefinite matrix completion problem with a rank constraint
• Selected open problems in discrete geometry and optimization
• Lectures on nonnegative polynomials and sums of squares
• Realizability of graphs
• Realizability of graphs in three dimensions

This page was built for publication: The Gram dimension of a graph

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