  


The Gram dimension of a graph
Monique Laurent(M.Laurentcwi.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 3realizable 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 ) Citation: Download: [PDF] Entry Submitted: 12/27/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  