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 the intersection graph of congruent spheres.^[1][2][3] The sphericity of a graph is one of several notions of graph dimension based on intersection graphs; others include boxicity and cubicity.^[4][5] The concept of sphericity was first introduced by Hiroshi Maehara in 1980^[6] and by V. J. Havel in 1982.^[7]

This article only considers undirected graphs, with finite and non-empty vertex sets, with no loop and no multiple edge.^[8][9]

The sphericity of a graph ${\displaystyle G}$, denoted by ${\displaystyle \operatorname {sph} (G)}$, is the smallest integer ${\displaystyle n\geq 0}$ such that ${\displaystyle G}$ can be realized as an intersection graph of open unit-radius ${\displaystyle n}$-disks,^[10] or of closed unit-diameter spheres,^[11] in the ${\displaystyle n}$-dimensional Euclidean space, ${\displaystyle \mathbb {R} ^{n}}$.^[12] (The final result is the same.)

Sphericity can also be defined using the language of space graphs as follows. For a finite set of points in the ${\displaystyle n}$-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 its adjacency limit).^[13]
Then, the sphericity of a graph ${\displaystyle G}$ is the minimum ${\displaystyle n}$ such that ${\displaystyle G}$ is isomorphic to a space graph in ${\displaystyle \mathbb {R} ^{n}}$.^[14]

Graphs of sphericity ${\displaystyle 1}$ are known as unit interval graphs^[15] or indifference graphs. Graphs of sphericity ${\displaystyle 2}$ 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.^[16] (Here, ${\displaystyle n}$ doesn't denote the space dimension, but the graph order.)

Graph	Description	Sphericity	Note
${\displaystyle K_{1}}$	Complete graph	${\displaystyle 0}$
${\displaystyle K_{n}}$	Complete graph	${\displaystyle 1}$	${\displaystyle n>1}$
${\displaystyle P_{n}}$	Path graph	${\displaystyle 1}$	${\displaystyle n>1}$
${\displaystyle C_{n}}$	Circuit graph	${\displaystyle 2}$	${\displaystyle n>3}$
${\displaystyle K_{m(2)}}$	Complete m-partite graph on ${\displaystyle m}$ sets of size ${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle m>1}$

However, Fishburn claims that ${\displaystyle \operatorname {cub} (G)=\operatorname {sph} (G)=0}$ if and only if ${\displaystyle G}$ is a complete graph (where ${\displaystyle \operatorname {cub} (G)}$ denotes the cubicity of ${\displaystyle G}$; by convention, ${\displaystyle 0}$-space is a point ${\displaystyle p}$ and any (closed) ${\displaystyle 0}$-disk = any (closed) ${\displaystyle 0}$-cube = ${\displaystyle \{p\}}$), and that ${\displaystyle \operatorname {cub} (G)=\operatorname {sph} (G)=1}$ if and only if ${\displaystyle G}$ is a unit interval graph that is not complete.^[17] Indeed, his definition of cubicity / sphericity allows adjacent distinct vertices with same closed neighborhood to be assigned the same cube / sphere.

The most general upper bound on sphericity that is known is as follows:
If a graph ${\displaystyle G}$ is not complete, then ${\displaystyle \operatorname {sph} (G)\leq |G|-\mathbb {\text{ω}} (G)}$,
where ${\displaystyle \mathbb {\text{ω}} (G)}$ denotes the clique number of ${\displaystyle G}$, and ${\displaystyle |G|}$ denotes the number of vertices of ${\displaystyle G}$.^[18][19]

For certain graphs, a slightly smaller upper bound is known:
If ${\displaystyle G}$ is a split graph and ${\displaystyle |G|-\mathbb {\mbox{ω}} (G)>2}$, then ${\displaystyle \operatorname {sph} (G)\leq |G|-\mathbb {\mbox{ω}} (G)-1}$.^[20]

For every positive integer ${\displaystyle m}$, there exists a split graph ${\displaystyle G}$ such that ${\displaystyle \operatorname {sph} (G)=|G|-\mathbb {\text{ω}} (G)-1=m}$.^[21]