Sphericity (graph theory)
In the mathematical field of graph theory, the sphericity of a graph is a graph invariant defined to be the smallest dimension of Euclidean space required to realize the graph as an intersection graph of unit-radius spheres, or of unit-diameter spheres. The sphericity of a graph is one of several notions of graph dimension based on intersection graphs; others include boxicity and cubicity. The concept of sphericity was first introduced by Hiroshi Maehara in the early 1980s.
Definitions
Let be an undirected graph with finite and non-empty vertex set, with no loop and no multiple edge. Then the sphericity of, denoted by, is the smallest integer such that can be realized as an intersection graph of open unit-radius spheres, or of closed unit-diameter spheres, in the -dimensional Euclidean space,.Sphericity can also be defined using the language of space graphs as follows. For a finite set of points in the -dimensional Euclidean space, a space graph is built by connecting pairs of points with a line segment if and only if their Euclidean distance is less than some specified constant.
Then, the sphericity of a graph is the minimum such that is isomorphic to a space graph in.
Graphs of sphericity are known as unit interval graphs or indifference graphs. Graphs of sphericity are known as unit disk graphs.
Bounds
The sphericity of certain graph classes can be computed exactly. The following sphericities were given by Maehara on page 56 of his original paper on the topic.| Graph | Description | Sphericity | Notes |
| Complete graph | |||
| Complete graph | |||
| Path graph | |||
| Circuit graph | |||
| Complete m-partite graph on sets of size |
The most general upper bound on sphericity that is known is as follows:
If a graph is not complete, then,
where denotes the clique number of, and denotes the number of vertices of.