Dot product representation of a graph

From HandWiki

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 Fk such that xy is an edge of G if and only if f(xf(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

See also

References

  1. 1.0 1.1 1.2 1.3 Fiduccia, Charles M. (1998), "Dot product representations of graphs", Discrete Mathematics 181 (1-3): 113–138, doi:10.1016/S0012-365X(97)00049-6 .
  2. 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 .
  3. 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 .
  4. Kang, Ross J. (2011), "Dot product representations of planar graphs", Electronic Journal of Combinatorics 18 (1): Paper 216 .

External links