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.{{citation
| last1 = Fiduccia | first1 = Charles M.
| last2 = Scheinerman | first2 = Edward R. | author2-link = Ed Scheinerman
| last3 = Trenk | first3 = Ann | author3-link = Ann Trenk
| last4 = Zito | first4 = Jennifer S.
| doi = 10.1016/S0012-365X(97)00049-6
| issue = 1–3
| journal = Discrete Mathematics
| mr = 1600755
| pages = 113–138
| title = Dot product representations of graphs
| volume = 181
| year = 1998| doi-access = free
}}.{{citation
| last1 = Reiterman | first1 = J.
| last2 = Rödl | first2 = V.
| last3 = Šiňajová | first3 = E.
| doi = 10.1007/BF02187736
| issue = 4
| journal = Discrete & Computational Geometry
| mr = 996768
| pages = 349–364
| title = Embeddings of graphs in Euclidean spaces
| volume = 4
| year = 1989| doi-access = free
}}.{{citation
| last1 = Reiterman | first1 = J.
| last2 = Rödl | first2 = V.
| last3 = Šiňajová | first3 = E.
| doi = 10.1016/0095-8956(92)90002-F
| issue = 1
| journal = Journal of Combinatorial Theory
| mr = 1182453
| pages = 1–8
| series = Series B
| title = On embedding of graphs into Euclidean spaces of small dimension
| volume = 56
| year = 1992| doi-access = free
}}.
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(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.
Properties
- A threshold graph is a dot product graph with positive t and dot product dimension 1.
- Every interval graph has dot product dimension at most 2.
- Every planar graph has dot product dimension at most 4.{{citation
| last1 = Kang | first1 = Ross J.
| last2 = Lovász | first2 = László | author2-link = László Lovász
| last3 = Müller | first3 = Tobias
| last4 = Scheinerman | first4 = Edward R.
| issue = 1
| journal = Electronic Journal of Combinatorics
| mr = 2853073
| page = Paper 216
| title = Dot product representations of planar graphs
| volume = 18
| year = 2011| doi = 10.37236/703
}}.
See also
References
{{reflist}}
External links
- {{Commonscatinline|Matrix representation of graphs}}