Sphericity (graph theory)

Example of a graph with sphericity 2: A space graph of the vertices of a pentagon, realized as the intersection graph of the unit disks, in the plane, centered on these points; this is 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]

Example of a graph with sphericity 1: An indifference graph, formed from a set of points, on the real number line, by connecting pairs of points whose distance is at most 1. Also the intersection graph of the set of unit intervals centered on the points.

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 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}$. ^{[1] [6]}

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}$. ^[1]

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}$. ^[1]

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 Tutte, W. T. (ed.), Recent Progress in Combinatorics (PDF), San Diego, CA: Academic Press, pp. 301–310, 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|-\mathbb {\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|-\mathbb {\text{ω}} (G)}$ extends to complete graphs (not only to ${\displaystyle K_{1}}$).