The gram dimension of a graph

M. Laurent, A. Varvitsiotis

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

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 Kk + 1. We show that a graph has Gram dimension at most 4 if and only if it does not have K5 and K2,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 languageEnglish
Title of host publicationProceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012)
EditorsA.R. Mahjoub, V. Markakis, I. Milis, V. Paschos
Place of PublicationBerlin Heidelberg
PublisherSpringer Verlag
Pages356-367
Volume7422
ISBN (Print)9783642321467
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
Volume7422

Fingerprint

Graph in graph theory
Forbidden Minor
Unit vector
Minor
Assignment
Realizability
Scalar, inner or dot product
If and only if
Imply
Closed
Integer
Vertex of a graph

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). Berlin Heidelberg: Springer Verlag.
Laurent, M. ; Varvitsiotis, A. / The gram dimension of a graph. Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012). editor / A.R. Mahjoub ; V. Markakis ; I. Milis ; V. Paschos. Vol. 7422 Berlin Heidelberg : Springer Verlag, 2012. pp. 356-367 (Lecture Notes in Computer Science).
@inproceedings{39190795a5b84dc3bafef77865228e99,
title = "The gram dimension of a graph",
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 Kk + 1. We show that a graph has Gram dimension at most 4 if and only if it does not have K5 and K2,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].",
author = "M. Laurent and A. Varvitsiotis",
year = "2012",
language = "English",
isbn = "9783642321467",
volume = "7422",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "356--367",
editor = "A.R. Mahjoub and V. Markakis and I. Milis and V. Paschos",
booktitle = "Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012)",
address = "Germany",

}

Laurent, M & Varvitsiotis, A 2012, The gram dimension of a graph. in AR Mahjoub, V Markakis, I Milis & V Paschos (eds), Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012). vol. 7422, Lecture Notes in Computer Science, vol. 7422, Springer Verlag, Berlin Heidelberg, pp. 356-367.

The gram dimension of a graph. / Laurent, M.; Varvitsiotis, A.

Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012). ed. / A.R. Mahjoub; V. Markakis; I. Milis; V. Paschos. Vol. 7422 Berlin Heidelberg : Springer Verlag, 2012. p. 356-367 (Lecture Notes in Computer Science; Vol. 7422).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

TY - GEN

T1 - The gram dimension of a graph

AU - Laurent, M.

AU - Varvitsiotis, A.

PY - 2012

Y1 - 2012

N2 - 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 Kk + 1. We show that a graph has Gram dimension at most 4 if and only if it does not have K5 and K2,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].

AB - 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 Kk + 1. We show that a graph has Gram dimension at most 4 if and only if it does not have K5 and K2,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].

M3 - Conference contribution

SN - 9783642321467

VL - 7422

T3 - Lecture Notes in Computer Science

SP - 356

EP - 367

BT - Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012)

A2 - Mahjoub, A.R.

A2 - Markakis, V.

A2 - Milis, I.

A2 - Paschos, V.

PB - Springer Verlag

CY - Berlin Heidelberg

ER -

Laurent M, Varvitsiotis A. The gram dimension of a graph. In Mahjoub AR, Markakis V, Milis I, Paschos V, editors, Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO 2012). Vol. 7422. Berlin Heidelberg: Springer Verlag. 2012. p. 356-367. (Lecture Notes in Computer Science).