2012/04/03 by Monique Laurent, Laurent, Monique, Antonios Varvitsiotis +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Topological and Geometric Data Analysis #cs.DM #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1204.0734
31 pages, 6 Figures. arXiv admin note: substantial text overlap with arXiv:1112.5960
arxiv created 2012/04/03 · openalex publication_date 2012/04/03 · arxiv updated 2012/04/04 · openalex created_date 2022/09/27 · openalex updated_date 2026/07/28
The Gram dimension \gd(G) of a graph G is the smallest integer k≥ 1 such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of G, can be completed to a positive semidefinite matrix of rank at most k (assuming a positive semidefinite completion exists). For any fixed k the class of graphs satisfying \gd(G) ≤ k is minor closed, hence it can characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is Kk+1 for k≤ 3 and that there are two minimal forbidden minors: K5 and K2,2,2 for k=4. We also show some close connections to Euclidean realizations of graphs and to the graph parameter ν^=(G) of \citeH03. In particular, our characterization of the graphs with \gd(G)≤ 4 implies the forbidden minor characterization of the 3-realizable graphs of Belk and Connelly \citeBelk,BC and of the graphs with ν^=(G) ≤ 4 of van der Holst \citeH03.