A dot product representation of a simple graph is a method of representing a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
using vector spaces and the dot product from
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
. Every graph has a dot product representation.
[.]
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.
Properties
* A
threshold graph
In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:
# Addition of a single isolated vertex to the graph.
# Addition of a single dominating vertex t ...
is a dot product graph with positive t and dot product dimension 1.
* Every
interval graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,
with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
In ...
has dot product dimension at most 2.
* Every
planar graph has dot product dimension at most 4.
[.]
See also
*
Adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
References
External links
*{{Commonscatinline, Matrix representation of graphs
Graph theory