### Abstract

The Gram dimension \rm gd(

*G)*of a graph is the smallest integer*k*≥ 1 such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment of unit vectors lying in ℝ^{k}, having the same inner products on the edges of the graph. The class of graphs satisfying \rm gd*(G)*≤*k*is minor closed for fixed*k*, so it can characterized by a finite list of forbidden minors. For*k*≤ 3, the only forbidden minor is*K*. We show that a graph has Gram dimension at most 4 if and only if it does not have K_{k + 1}_{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 [5,6].Original language | English |
---|---|

Title of host publication | Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012) |

Editors | A.R. Mahjoub, V. Markakis, I. Milis, V. Paschos |

Place of Publication | Berlin Heidelberg |

Publisher | Springer Verlag |

Pages | 356-367 |

Volume | 7422 |

ISBN (Print) | 9783642321467 |

Publication status | Published - 2012 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 7422 |

## Fingerprint Dive into the research topics of 'The gram dimension of a graph'. Together they form a unique fingerprint.

## Cite this

Laurent, M., & Varvitsiotis, A. (2012). The gram dimension of a graph. In A. R. Mahjoub, V. Markakis, I. Milis, & V. Paschos (Eds.),

*Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012)*(Vol. 7422, pp. 356-367). (Lecture Notes in Computer Science; Vol. 7422). Springer Verlag. http://link.springer.com/chapter/10.1007/978-3-642-32147-4_32