Header menu link for other important links
X
Boxicity and cubicity of product graphs
L.S. Chandran, W. Imrich, R. Mathew,
Published in Academic Press
2015
Volume: 48
   
Pages: 100 - 109
Abstract
The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in Rk. 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 d, of the boxicity and the cubicity of the dth 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 dth Cartesian power of any given finite graph is, respectively, in O(log. d/log. log. d) and Θ (d/log. d). 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. © 2015 Elsevier Ltd.
About the journal
JournalEuropean Journal of Combinatorics
PublisherAcademic Press
ISSN01956698