Sphericity (graph theory)

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] (${\displaystyle n}$ denotes 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_{p(2)}}$	Complete multipartite graph on ${\displaystyle p}$ parts of cardinal ${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle p>1.}$[17]

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 the singleton ${\displaystyle \{0\}}$ and any (closed) ${\displaystyle 0}$-disk = any (closed) ${\displaystyle 0}$-cube = ${\displaystyle \{0\}}$), 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.^[18] Indeed, his definition of cubicity / sphericity allows adjacent distinct vertices with same closed neighborhood to be assigned the same cube / sphere.^[19][20]

The following sphericities were given by Maehara in his paper on semiregular polyhedra.

Graph of polyhedron	Description	Sphericity	Note	Ref.
${\displaystyle A_{m}}$	${\displaystyle m}$-Antiprism	${\displaystyle 2}$	${\displaystyle m\geq 3}$	[21]
${\displaystyle P_{m}}$	${\displaystyle m}$-Prism	${\displaystyle 2}$	${\displaystyle m=3}$ or ${\displaystyle m\geq 10}$	[22]
${\displaystyle P_{m}}$	${\displaystyle m}$-Prism	${\displaystyle 3}$	${\displaystyle m=5}$ or ${\displaystyle m=6}$	[23]
${\displaystyle C,D,I}$	Cube, regular dodecahedron, regular icosahedron	${\displaystyle 3}$		[24]
	Archimedean solid	${\displaystyle 3}$		[25]

Maehara conjectured that the graphs of the ${\displaystyle 7}$-prism, ${\displaystyle 8}$-prism, and ${\displaystyle 9}$-prism have sphericity ${\displaystyle 3}$.^[26]

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 |G|}$ and ${\displaystyle \mathbb {\text{ω}} (G)}$ respectively denote the order and the clique number of ${\displaystyle G}$.^[27][28]

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

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

For ${\displaystyle 1\leq m\leq n}$, ${\displaystyle ~\operatorname {sph} (K_{m,n})\leq m-1+\lceil n/2\rceil }$, where ${\displaystyle K_{m,n}}$ denotes the complete bipartite graph with part cardinals ${\displaystyle m}$ and ${\displaystyle n}$.^[31][32]