### Abstract

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 be characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is K

_{k+1}for k≤3 and that there are two minimal forbidden minors: K_{5}and K_{2,2,2}for k=4 . We also show some close connections to Euclidean realizations of graphs and to the graph parameter ν=(G) of van der Holst (Combinatorica 23(4):633–651, 2003). In particular, our characterization of the graphs with gd(G)≤4 implies the forbidden minor characterization of the 3-realizable graphs of Belk (Discret Comput Geom 37:139–162, 2007) and Belk and Connelly (Discret Comput Geom 37:125–137, 2007) and of the graphs with ν=(G)≤4 of van der Holst (Combinatorica 23(4):633–651, 2003).Original language | English |
---|---|

Pages (from-to) | 291-325 |

Journal | Mathematical Programming |

Volume | 145 |

Issue number | 1-2 |

Early online date | 16 Feb 2013 |

DOIs | |

Publication status | Published - Jun 2014 |

## Fingerprint Dive into the research topics of 'A new graph parameter related to bounded rank positive semidefinite matrix completions'. Together they form a unique fingerprint.

## Cite this

Laurent, M., & Varvitsiotis, A. (2014). A new graph parameter related to bounded rank positive semidefinite matrix completions.

*Mathematical Programming*,*145*(1-2), 291-325. https://doi.org/10.1007%2fs10107-013-0648-x#page-1