Cubicity
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. 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. with cubicity , realized as the intersection graph of unit -cubes, i.e. unit intervals, on the real number line.
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. 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. with cubicity , realized as the intersection graph of unit -cubes, i.e. unit intervals, on the real number line. For a graph G , \operatorname{cub}(G) = 0 if and only if G is complete. For a graph G , \operatorname{cub}(G) = 1 if and only if G is a unit interval graph that is not complete. For n \in \N^* , \operatorname{cub}(K_{1,n}) = \lfloor \log_2 (2n-1) \rfloor , where K_{1,n} denotes the star graph, a tree with one internal vertex and n leaves, and where \lfloor \cdot \rfloor denotes the floor function. For p \in \N^* , \operatorname{cub}(K_{p(2)}) = p , where K_{p(2)} denotes the complete multipartite graph with p parts of cardinal 2 . For a graph G on n vertices, \operatorname{cub}(G) \leq \lfloor 2n/3 \rfloor . Moreover, this upper bound is best possible in terms of n . For certain graphs, cubicity exceeds sphericity; the five-pointed star, K_{1,5}, is an example: ~ \operatorname{cub}(K_{1,5}) = 3 > \operatorname{sph}(K_{1,5}) = 2. In the other direction, graphs G can be constructed so that ~ \operatorname{sph}(G) > \operatorname{cub}(G) = k, ~ for k \in \{ 2,3 \}.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371587116 under CC BY-SA 4.0; modifications have been made.