The Gram dimension of a graph

Details The Gram dimension of a graph The Gram dimension of a graph

2011-12-27

arxiv.org/abs/1112.5960v2

Mathematics

Combinatorics

12 pages, 1 Figure. Extended abstract to appear in the proceedings of ISCO 2012. The full version of the paper is available un

Scientific paper

The Gram dimension $\gd(G)$ of a graph is the smallest integer $k \ge 1$ such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment of unit vectors lying in $\oR^k$, having the same inner products on the edges of the graph. The class of graphs satisfying $\gd(G) \le k$ is minor closed for fixed $k$, so it can characterized by a finite list of forbidden minors. For $k\le 3$, the only forbidden minor is $K_{k+1}$. We show that a graph has Gram dimension at most 4 if and only if it does not have $K_5$ and $K_{2,2,2}$ as minors. We also show some close connections to the notion of $d$-realizability of graphs. In particular, our result implies the characterization of 3-realizable graphs of Belk and Connelly \cite{Belk,BC}.

Affiliated with

Also associated with

No associations

Rating

The Gram dimension of a graph 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 The Gram dimension of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Gram dimension of a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-37250