Dot product representation of a graph
A dot product representation of a simple graph is a method of representing a graph using vector spaces and the dot product from linear algebra. Every graph has a dot product representation.^{[1]}^{[2]}^{[3]}
Definition
Let G be a graph with vertex set V. Let F be a field, and f a function from V to F^{k} such that xy is an edge of G if and only if f(x)·f(y) ≥ t. This is the dot product representation of G. The number t is called the dot product threshold, and the smallest possible value of k is called the dot product dimension.^{[1]}
Properties
- A threshold graph is a dot product graph with positive t and dot product dimension 1.^{[1]}
- Every interval graph has dot product dimension at most 2.^{[1]}
- Every planar graph has dot product dimension at most 4.^{[4]}
References
- ^ ^{a} ^{b} ^{c} ^{d} Fiduccia, Charles M.; Scheinerman, Edward R.; Trenk, Ann; Zito, Jennifer S. (1998), "Dot product representations of graphs", Discrete Mathematics, 181 (1-3): 113–138, doi:10.1016/S0012-365X(97)00049-6, MR 1600755.
- ^ Reiterman, J.; Rödl, V.; Šiňajová, E. (1989), "Embeddings of graphs in Euclidean spaces", Discrete & Computational Geometry, 4 (4): 349–364, doi:10.1007/BF02187736, MR 0996768.
- ^ Reiterman, J.; Rödl, V.; Šiňajová, E. (1992), "On embedding of graphs into Euclidean spaces of small dimension", Journal of Combinatorial Theory, Series B, 56 (1): 1–8, doi:10.1016/0095-8956(92)90002-F, MR 1182453.
- ^ Kang, Ross J.; Lovász, László; Müller, Tobias; Scheinerman, Edward R. (2011), "Dot product representations of planar graphs", Electronic Journal of Combinatorics, 18 (1): Paper 216, MR 2853073.
This page is based on the copyrighted Wikipedia article "Dot product representation of a graph"; it is used under the Creative Commons
Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may
redistribute it, verbatim or modified, providing that you comply with
the terms of the CC-BY-SA