Cubicity

From HandWiki

In the mathematical field of graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as the intersection graph of axis-parallel unit cubes in Euclidean space.[1] Cubicity was introduced by Fred S. Roberts in 1969, along with a related invariant called boxicity that considers the smallest dimension needed to represent a graph as the intersection graph of axis-parallel rectangles in Euclidean space.[2]

An indifference graph with cubicity 1, realized as the intersection graph of unit 1-cubes, i.e. unit intervals, on the real number line.

Definition

This article only considers simple, undirected graphs, with finite and non-empty vertex sets.[3][4]

The cubicity of a graph G, denoted by cub⁡(G), is the smallest integer k such that G can be represented as the intersection graph of axis-parallel closed unit k-cubes in k-dimensional Euclidean space, Ek.[5][6][7]

For k≥1, a graph G can have such a representation in Ek if and only if G is the intersection of k indifference graphs on the same vertex set as G.[8]

The cubicity of a complete graph is defined to be zero.[9]

Relations to certain graph classes, upper bound

For a graph G,cub⁡(G)=0 if and only if G is complete.[10]

For a graph G,cub⁡(G)=1 if and only if G is a unit interval graph that is not complete.[11]

For n∈ℕ*,cub⁡(K1,n)=⌊log2(2n−1)⌋, where K1,n denotes the star graph of (1 center and) n vertices, and ⌊⋅⌋ denotes the floor function.[12][13]

For p∈ℕ*,cub⁡(Kp(2))=p, where Kp(2) denotes the complete multipartite graph with p parts of cardinal 2.[14][15]

For a graph G on n vertices, cub⁡(G)≤⌊2n/3⌋. Moreover, this upper bound is best possible in terms of n.[16][17]

Relations to other graph dimensions

Relations to boxicity: bounds

The cubicity of a graph G is closely related to its boxicity, denoted by box⁡(G). The definition of boxicity is essentially the same as that of cubicity, but with axis-parallel boxes instead of axis-parallel unit cubes.

Since a cube is a special case of a box, the cubicity of a graph G is always an upper bound for its boxicity, i.e., box⁡(G)≤cub⁡(G).

In the other direction, it can be shown that for a graph G on n vertices, cub⁡(G)≤⌈log2n⌉box⁡(G), where ⌈⋅⌉ denotes the ceiling function. Moreover, this upper bound is tight.[18]

Relations to sphericity

The sphericity of a graph G, denoted by sph⁡(G), is defined in the same way as cubicity but with congruent spheres instead of axis-parallel unit cubes.

For certain graphs, cubicity exceeds sphericity; the five-pointed star, K1,5, is an example: cub⁡(K1,5)=3>sph⁡(K1,5)=2.[19]

In the other direction, graphs G can be constructed so that sph⁡(G)>cub⁡(G)=k, for k∈{2,3}.[20]

Notes

  1. ↑ (Fishburn 1983)
  2. ↑ (Roberts 1969)
  3. ↑ (Chandran Mathew)
  4. ↑ (Fishburn 1983)
  5. ↑ (Roberts 1969) uses closed cubes of side-length 1.
    Footnote 1 on p. 302: "Boxes are not necessarily closed, though it is not hard to show that if a representation [of G] is attainable with [open] boxes in Ek, it is attainable with closed boxes in Ek.".
  6. ↑ (Chandran Mathew) use Cartesian products of closed intervals [ai,ai+1].
  7. ↑ (Fishburn 1983)
  8. ↑ (Roberts 1969)
    Indeed: ∀u,v∈V(G), {u,v}∈E(G) iff ‖f(u)−f(v)‖∞≤1, iff ∀1≤i≤k,|fi(u)−fi(v)|≤1, i.e., {u,v}∈E(Gi).
    And so: ∀u,w∈V(G), {u,w}∉E(G) iff ‖f(u)−f(w)‖∞>1, iff ∃1≤i≤k such that |fi(u)−fi(w)|>1, i.e., {u,w}∉E(Gi);
    but ∀1≤j≠i≤k,|fj(u)−fj(w)| may be ≤1, i.e., {u,w} may ∈E(Gj).
  9. ↑ (Chandran Mathew)
  10. ↑ (Roberts 1969)
  11. ↑ (Fishburn 1983)
  12. ↑ (Roberts 1969)
  13. ↑ That is, cub(K1,n) = ⌈log₂(n)⌉. Proof: ∀ n ∈ ℕ*, 1 ≤ n; so, 0 < n ≤ 2n−1. ∀ n ∈ ℕ*, ∃! c ∈ ℕ such that n ≤ 2ᶜ ≤ 2n−1 (namely, c is the least k ∈ ℕ such that n ≤ 2ᵏ); so, ∃! c ∈ ℕ such that log₂(n) ≤ c ≤ log₂(2n−1). So, ⌈log₂(n)⌉ = c = ⌊log₂(2n−1)⌋.
  14. ↑ (Fishburn 1983)
  15. ↑ (Roberts 1969)
  16. ↑ (Fishburn 1983)
  17. ↑ (Roberts 1969)
  18. ↑ (Chandran Mathew)
  19. ↑ (Fishburn 1983)
  20. ↑ (Fishburn 1983)

References



Retrieved from "https://handwiki.org/wiki/index.php?title=Cubicity&oldid=4415518"