Optimization Online


The Gram dimension of a graph

Monique Laurent(M.Laurent***at***cwi.nl)
Antonios Varvitsiotis(A.Varvitsiotis***at***cwi.nl)

Abstract: The Gram dimension $\gd(G)$ of a graph is the smallest integer $k \ge 1$ such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment of unit vectors lying in $\oR^k$, having the same inner products on the edges of the graph. The class of graphs satisfying $\gd(G) \le k$ is minor closed for fixed $k$, so it can characterized by a finite list of forbidden minors. For $k\le 3$, 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.

Keywords: positive semidefinite matrix completion, semidefinite programming, geometric graph representations, Euclidean distance matrix, realizability of graphs

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 12/27/2011
Entry Accepted: 12/28/2011
Entry Last Modified: 12/27/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society