Mathematics – Optimization and Control
Scientific paper
2012-04-03
Mathematics
Optimization and Control
31 pages, 6 Figures. arXiv admin note: substantial text overlap with arXiv:1112.5960
Scientific paper
The Gram dimension $\gd(G)$ of a graph $G$ is the smallest integer $k\ge 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) \le k$ is minor closed, hence it can characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is $K_{k+1}$ for $k\le 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 \cite{H03}. In particular, our characterization of the graphs with $\gd(G)\le 4$ implies the forbidden minor characterization of the 3-realizable graphs of Belk and Connelly \cite{Belk,BC} and of the graphs with $\nu^=(G) \le 4$ of van der Holst \cite{H03}.
Laurent Monique
Varvitsiotis Antonios
No associations
LandOfFree
A new graph parameter related to bounded rank positive semidefinite matrix completions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A new graph parameter related to bounded rank positive semidefinite matrix completions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new graph parameter related to bounded rank positive semidefinite matrix completions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-355458