Sphericity (graph theory)
In 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 unit spheres. The sphericity of a graph is a generalization of the boxicity and cubicity invariants defined by F.S. Roberts in the late 1960s.[1][2] The concept of sphericity was first introduced by Hiroshi Maehara in the early 1980s.[3]
Definition
Let [math]\displaystyle{ G }[/math] be a graph. Then the sphericity of [math]\displaystyle{ G }[/math], denoted by [math]\displaystyle{ \operatorname{sph}(G) }[/math], is the smallest integer [math]\displaystyle{ n }[/math] such that [math]\displaystyle{ G }[/math] can be realized as an intersection graph of unit spheres in [math]\displaystyle{ n }[/math]-dimensional Euclidean space [math]\displaystyle{ \mathbb R^n }[/math].[4]
Sphericity can also be defined using the language of space graphs as follows. For a finite set of points in some [math]\displaystyle{ n }[/math]-dimensional Euclidean space, a space graph is built by connecting pairs of points with a line segment when their Euclidean distance is less than some specified constant. Then the sphericity of a graph [math]\displaystyle{ G }[/math] is the minimum [math]\displaystyle{ n }[/math] such that [math]\displaystyle{ G }[/math] is isomorphic to a space graph in [math]\displaystyle{ \mathbb R^n }[/math].[3]
Graphs of sphericity 1 are known as interval graphs or indifference graphs. Graphs of sphericity 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.
| Graph | Description | Sphericity | Notes |
|---|---|---|---|
| [math]\displaystyle{ K_1 }[/math] | Complete graph | 0 | |
| [math]\displaystyle{ K_n }[/math] | Complete graph | 1 | [math]\displaystyle{ n\gt 1 }[/math] |
| [math]\displaystyle{ P_n }[/math] | Path graph | 1 | [math]\displaystyle{ n\gt 1 }[/math] |
| [math]\displaystyle{ C_n }[/math] | Circuit graph | 2 | [math]\displaystyle{ n\gt 3 }[/math] |
| [math]\displaystyle{ K_{m(2)} }[/math] | Complete m-partite graph on m sets of size 2 | 2 | [math]\displaystyle{ m \gt 1 }[/math] |
The most general known upper bound on sphericity is as follows. Assuming the graph is not complete, then [math]\displaystyle{ \operatorname{sph}(G) \leq |G| - \omega(G) }[/math] where [math]\displaystyle{ \omega(G) }[/math] is the clique number of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ |G| }[/math] denotes the number of vertices of [math]\displaystyle{ G. }[/math][3]
References
- ↑ 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
- ↑ Fishburn, Peter C (1983-12-01). "On the sphericity and cubicity of graphs" (in en). Journal of Combinatorial Theory, Series B 35 (3): 309–318. doi:10.1016/0095-8956(83)90057-6. ISSN 0095-8956. https://www.sciencedirect.com/science/article/pii/0095895683900576.
- ↑ 3.0 3.1 3.2 Maehara, Hiroshi (1984-01-01). "Space graphs and sphericity" (in en). Discrete Applied Mathematics 7 (1): 55–64. doi:10.1016/0166-218X(84)90113-6. ISSN 0166-218X. https://www.sciencedirect.com/science/article/pii/0166218X84901136.
- ↑ Maehara, Hiroshi (1986-03-01). "On the sphericity of the graphs of semiregular polyhedra" (in en). Discrete Mathematics 58 (3): 311–315. doi:10.1016/0012-365X(86)90150-0. ISSN 0012-365X. https://www.sciencedirect.com/science/article/pii/0012365X86901500.
 |  |
