20120101
The Gram dimension of a graph
Publication
Publication
Presented at the
International Symposium on Combinatorial Optimization
The Gram dimension gd(G) of a graph is the smallest integer k ≥ 1 such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment of unit vectors lying in Rk, having the same inner products on the edges of the graph. The class of graphs satisfying gd(G) ≤ k is minor closed for fixed k, so it can characterized by a finite list of forbidden minors. For k ≤ 3, the only forbidden minor is Kk+1. We show that a graph has Gram dimension at most 4 if and only if it does not have K5 and K2,2,2 as minors. We also show some close connections to the notion of drealizability of graphs. In particular, our result implies the characterization of 3realizable graphs of Belk and Connelly.
Additional Metadata  

Keywords  matrix completion, semidefinite programming, graph realization, Gram dimension, Euclidean embedding 
THEME  Logistics (theme 3) 
Publisher  Springer 
Editor  A.R. Mahjoub , V. Markakis (Vangelis) , I. Millis , V. Paschos 
Series  Lecture Notes in Computer Science 
Project  Semidefinite programming and combinatorial optimization 
Conference  International Symposium on Combinatorial Optimization 
Citation 
Laurent, M, & Varvitsiotis, A. (2012). The Gram dimension of a graph. In A.R Mahjoub, V Markakis, I Millis, & V Paschos (Eds.), Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012) (pp. 356–367). Springer.

Additional Files  

Fulltext Final Version  
Publisher Version 
See Also 

techReport

techReport

techReport
