Sphericity (graph theory)

A space graph of the vertices of a pentagon, realized as an intersection graph of congruent disks in the plane. This is an example of a graph with sphericity 2, also known as a unit disk graph.

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 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] [2]} The concept of sphericity was first introduced by Hiroshi Maehara in the early 1980s. ^[1]

Definitions

Let ${\displaystyle G}$ be an undirected graph with finite and non-empty vertex set, with no loop and no multiple edge. Then the sphericity of ${\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 spheres, ^[1] or of closed unit-diameter spheres, ^[2] in the ${\displaystyle n}$-dimensional Euclidean space, ${\displaystyle \mathbb {R} ^{n}}$. ^[5] (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). ^[1]
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}}$. ^[1]

Graphs of sphericity ${\displaystyle 1}$ are known as unit interval graphs ^[1] or indifference graphs. Graphs of sphericity ${\displaystyle 2}$ 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. (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, on his page 310, 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 ${\displaystyle 0}$-sphere = any ${\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. Indeed, his definition of an intersection graph allows distinct vertices with same open neighborhood to be assigned the same 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|-{\text{ω}}(G)}$,
where ${\displaystyle \operatorname {\text{ω}} (G)}$ denotes the clique number of ${\displaystyle G}$, and ${\displaystyle |G|}$ denotes the number of vertices of ${\displaystyle G}$. ^{[1] [6]}

References

1. Maehara, Hiroshi (1984-01-01). "Space graphs and sphericity" . Discrete Applied Mathematics. 7 (1): 55–64. doi:10.1016/0166-218X(84)90113-6. ISSN   0166-218X.
2. Fishburn, Peter C. (1983-12-01). "On the sphericity and cubicity of graphs" . Journal of Combinatorial Theory, Series B. 35 (3): 309–318. doi:10.1016/0095-8956(83)90057-6. ISSN   0095-8956.
3. Hiroshi Maehara states: "A space graph in ${\displaystyle n}$-space is, as an abstract graph, nothing but the intersection graph of a family of equiradial ${\displaystyle n}$-discs in ${\displaystyle n}$-space.".
4. Roberts, F. S. (1969). On the boxicity and cubicity of a graph. In W. T. Tutte (Ed.), Recent Progress in Combinatorics (pp. 301–310). San Diego, CA: Academic Press. ISBN 978-0-12-705150-5.
5. Maehara, Hiroshi (1986-03-01). "On the sphericity of the graphs of semiregular polyhedra". Discrete Mathematics. 58 (3): 311–315. doi: 10.1016/0012-365X(86)90150-0 . ISSN   0012-365X.
6. Note: For a complete graph ${\displaystyle G}$ of any order ${\displaystyle n\geq 1}$, ${\displaystyle ~|G|-\mathrm {\text{ω}} (G)=0}$. With Fishburn's definition of sphericity, for a complete graph ${\displaystyle G}$ of any order ${\displaystyle n\geq 1}$, ${\displaystyle ~\operatorname {sph} (G)=0}$; then, ${\displaystyle \operatorname {sph} (G)\leq |G|-{\rm {\text{ω}}}(G)}$ extends to complete graphs (not only to ${\displaystyle K_{1}}$).