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 the intersection graph of congruent 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 1980 (and also used by Timothy F. Havel in 1982).
This article only considers undirected graphs, with finite and non-empty vertex sets, with no loop and no multiple edge.
The sphericity of a graph , denoted by , is the smallest integer such that can be realized as the intersection graph 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 (called the adjacency limit of ).<br>Then, the sphericity of a graph is the minimum integer such that is isomorphic to a space graph in . Indeed: A space graph in -space is, as an abstract graph, nothing but the intersection graph of a family of equiradial -disks in -space. Remark: Maehara takes these disks to be open. (The final result is the same.)
Graphs of sphericity are known as unit interval graphs or indifference graphs. Graphs of sphericity are known as unit disk graphs.
The sphericity on certain graph classes can be computed exactly. The following sphericities were given by Maehara in his original paper on the topic ( denotes the graph order).
However, Fishburn claims that if and only if is a complete graph (where denotes the cubicity of ; by convention, -space is the singleton and any (closed) -disk = any (closed) -cube = ), and that if and only if is a unit interval graph that is not complete. Indeed, his definition of cubicity / sphericity allows adjacent distinct vertices with same closed neighborhood to be assigned the same cube / sphere.
The following sphericities were given by Maehara in his paper on semiregular polyhedra.
Maehara conjectured that the graphs of the -prism, -prism, and -prism have sphericity .
The most general upper bound on sphericity that is known is as follows:<br>If a graph is not complete, then ,<br>where and respectively denote the order and the clique number of .
For certain graphs, a slightly smaller upper bound is known:<br>If is a split graph and , then .
For every positive integer , there exists a split graph such that .
For , , where denotes the complete bipartite graph with part cardinals and .