Boxicity and Cubicity of product graphs
Research output: Contribution to journal › Article › Research › peer-review
Standard
In: European journal of combinatorics, Vol. 48.2015, No. August, 2015, p. 100 - 109.
Research output: Contribution to journal › Article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex - Download
}
RIS (suitable for import to EndNote) - Download
TY - JOUR
T1 - Boxicity and Cubicity of product graphs
AU - Chandran, Sunil L.
AU - Imrich, Wilfried
AU - Mathew, Rogers
AU - Rajendraprasad, Deepak
PY - 2015
Y1 - 2015
N2 - The boxicity (cubicity) of a graph is the minimum natural number such that can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in . In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of , of the boxicity and the cubicity of the th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the th Cartesian power of any given finite graph is, respectively, in and . On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products.
AB - The boxicity (cubicity) of a graph is the minimum natural number such that can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in . In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of , of the boxicity and the cubicity of the th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the th Cartesian power of any given finite graph is, respectively, in and . On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products.
KW - graphentheorie, kombinatorik
U2 - 10.1016/j.ejc.2015.02.013
DO - 10.1016/j.ejc.2015.02.013
M3 - Article
VL - 48.2015
SP - 100
EP - 109
JO - European journal of combinatorics
JF - European journal of combinatorics
SN - 0195-6698
IS - August
ER -
