Sphericity (graph theory)

A graph with sphericity Template:Math: A space graph of the vertices of a pentagon, realized as the intersection graph of the unit Template:Math-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 the intersection graph of congruent spheres.^[1]^[2] The sphericity of a graph is one of several notions of graph dimension based on intersection graphs; others include boxicity and cubicity.^[3]^[4] The concept of sphericity was first introduced by Hiroshi Maehara in 1980^[5] (and also used by Timothy F. Havel in 1982).^[6]

Definitions

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

The sphericity of a graph $G$ , denoted by $sph (G)$ , is the smallest integer $k \geq 0$ such that $G$ can be realized as the intersection graph of closed unit-diameter spheres,^[9]^[10] in the $k$ -dimensional Euclidean space, $ℝ^{k}$ .

Sphericity can also be defined using the language of space graphs as follows. For a finite set of points in the $k$ -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 $𝔾$ ).^[11]
Then, the sphericity of a graph $G$ is the minimum integer $k \geq 0$ such that $G$ is isomorphic to a space graph in $ℝ^{k}$ .^[12] Indeed: A space graph in $k$ -space is, as an abstract graph, nothing but the intersection graph of a family of equiradial $k$ -disks in $k$ -space.^[13] Remark: Maehara takes these disks to be open.^[14] (The final result is the same.)

A space graph with sphericity Template:Math, formed from a set of points on the real number line, by connecting pairs of points whose distance is at most Template:Math. Also the intersection graph of the set of unit Template:Math-disks, i.e. unit intervals, centered on the points.

Graphs of sphericity $1$ are known as unit interval graphs^[15] or indifference graphs. Graphs of sphericity $2$ are known as unit disk graphs.

Values on certain graph classes, bounds

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] ( $n$ denotes the graph order).


Graph	Description	Sphericity	Note
$K_{1}$	Complete graph	$0$
$K_{n}$	Complete graph	$1$	$n > 1$
$P_{n}$	Path graph	$1$	$n > 1$
$C_{n}$	Circuit graph	$2$	$n > 3$
$K_{p (2)}$	Complete multipartite graph on $p$ parts of cardinal $2$	$2$	$p > 1.$ ^[17]

However, Fishburn claims that $cub (G) = sph (G) = 0$ if and only if $G$ is a complete graph (where $cub (G)$ denotes the cubicity of $G$ ; by convention, $0$ -space is the singleton ${0}$ and any (closed) $0$ -disk = any (closed) $0$ -cube = ${0}$ ), and that $cub (G) = sph (G) = 1$ if and only if $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.
$A_{m}$	$m$ -Antiprism	$2$	$m \geq 3$	^[21]
$P_{m}$	$m$ -Prism	$2$	$m = 3$ or $m \geq 10$	^[22]
$P_{m}$	$m$ -Prism	$3$	$m = 5$ or $m = 6$	^[23]
$C, D, I$	Cube, regular dodecahedron, regular icosahedron	$3$		^[24]
	Archimedean solid	$3$		^[25]

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

The most general upper bound on sphericity that is known is as follows:
If a graph $G$ is not complete, then $sph (G) \leq | G | - ω (G)$ ,
where $| G |$ and $ω (G)$ respectively denote the order and the clique number of $G$ .^[27]^[28]

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

For every positive integer $m$ , there exists a split graph $G$ such that $sph (G) = | G | - ω (G) - 1 = m$ .^[30]

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

Notes

Template:Reflist

References

Template:Refbegin

Template:Refend

↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt: "As a similar type of graph-dimension, there are the boxicity and the cubicity.".
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt: "[…] we connect each pair $x_{i}, x_{j}, i \neq j$ , by a line segment whenever $‖ x_{i} - x_{j} ‖ < t$ , […]".
(I.e., $‖ m_{i j} - x_{i} ‖ < t / 2$ and $‖ m_{i j} - x_{j} ‖ < t / 2$ , where $m_{i j} = (x_{i} + x_{j}) / 2$ .)
↑ Template:Harvtxt: "The graphs of sphericity $1$ are intersection graphs of families of unit intervals, […].".
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt: "Figure 2 shows […]; the lined circles in the four corners are for [the $B$ vertices] $b_{1}, b_{3}, b_{7},$ and $b_{9},$ which are respectively equivalent to the four corner $A$ vertices.".
↑ Template:Harvtxt: "[…], two points [ $a$ and $b$ ] are equivalent if and only if they have the same «closed neighborhoods». […] (Map $a$ and $b$ onto the same point in $n$ -space.)".
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ For a complete graph $G$ of any order $n \geq 1$ , $| G | - ω (G) = 0$ . With Fishburn's definition of sphericity, for a complete graph $G$ of any order $n \geq 1$ , $sph (G) = 0$ . Then, $sph (G) \leq | G | - ω (G)$ extends to complete graphs (not only to $K_{1}$ ).
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt
↑ Template:Harvtxt mentions a different version:
" $sph (K_{m, n}) \leq m + ⌊ n / 2 ⌋$ ".
For odd $n$ , $m - 1 + ⌈ n / 2 ⌉ = m + ⌊ n / 2 ⌋$ , alright;
but for even $n$ , $m - 1 + ⌈ n / 2 ⌉ = m - 𝟏 + ⌊ n / 2 ⌋$ .

[1] Template:Harvtxt

[2] Template:Harvtxt

[3] Template:Harvtxt

[4] Template:Harvtxt: "As a similar type of graph-dimension, there are the boxicity and the cubicity.".

[5] Template:Harvtxt

[6] Template:Harvtxt

[7] Template:Harvtxt

[8] Template:Harvtxt

[9] Template:Harvtxt

[10] Template:Harvtxt

[11] Template:Harvtxt

[12] Template:Harvtxt

[13] Template:Harvtxt

[14] Template:Harvtxt: "[…] we connect each pair $x_{i}, x_{j}, i \neq j$ , by a line segment whenever $‖ x_{i} - x_{j} ‖ < t$ , […]".
(I.e., $‖ m_{i j} - x_{i} ‖ < t / 2$ and $‖ m_{i j} - x_{j} ‖ < t / 2$ , where $m_{i j} = (x_{i} + x_{j}) / 2$ .)

[15] Template:Harvtxt: "The graphs of sphericity $1$ are intersection graphs of families of unit intervals, […].".

[16] Template:Harvtxt

[17] Template:Harvtxt

[18] Template:Harvtxt

[19] Template:Harvtxt: "Figure 2 shows […]; the lined circles in the four corners are for [the $B$ vertices] $b_{1}, b_{3}, b_{7},$ and $b_{9},$ which are respectively equivalent to the four corner $A$ vertices.".

[20] Template:Harvtxt: "[…], two points [ $a$ and $b$ ] are equivalent if and only if they have the same «closed neighborhoods». […] (Map $a$ and $b$ onto the same point in $n$ -space.)".

[21] Template:Harvtxt

[22] Template:Harvtxt

[23] Template:Harvtxt

[24] Template:Harvtxt

[25] Template:Harvtxt

[26] Template:Harvtxt

[27] Template:Harvtxt

[28] For a complete graph $G$ of any order $n \geq 1$ , $| G | - ω (G) = 0$ . With Fishburn's definition of sphericity, for a complete graph $G$ of any order $n \geq 1$ , $sph (G) = 0$ . Then, $sph (G) \leq | G | - ω (G)$ extends to complete graphs (not only to $K_{1}$ ).

[29] Template:Harvtxt

[30] Template:Harvtxt

[31] Template:Harvtxt

[32] Template:Harvtxt mentions a different version:
" $sph (K_{m, n}) \leq m + ⌊ n / 2 ⌋$ ".
For odd $n$ , $m - 1 + ⌈ n / 2 ⌉ = m + ⌊ n / 2 ⌋$ , alright;
but for even $n$ , $m - 1 + ⌈ n / 2 ⌉ = m - 𝟏 + ⌊ n / 2 ⌋$ .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

Sphericity (graph theory)

Contents

Definitions

Values on certain graph classes, bounds

Notes

References

Navigation menu

Sphericity (graph theory)

Definitions

Values on certain graph classes, bounds

Notes

References

Navigation menu

Search