A new graph parameter related to bounded rank positive semidefinite matrix completions

The Gram dimension $mathrm{gd}(G)$ of a graph $G$ is the smallest integer $kge 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 $mathrm{gd}(G) le 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 $kle 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 $nu ^=(G)$ of van der Holst (Combinatorica 23(4):633–651, 2003). In particular, our characterization of the graphs with $mathrm{gd}(G)le 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 $nu ^=(G) le 4$ of van der Holst (Combinatorica 23(4):633–651, 2003).