Boxicity and cubicity of divisor graphs and power graphs

Abstract

The boxicity (cubicity) of an undirected graph Γ is the smallest non-negative integer k such that Γ can be represented as the intersection graph of axis-parallel rectangular boxes (unit cubes) in Rk. An undirected graph is classified as a comparability graph if it is isomorphic to the comparability graph of some partial order. This paper studies boxicity and cubicity for subclasses of comparability graphs.

We initiate the study of boxicity and cubicity of a special class of algebraically defined comparability graphs, namely the power graphs. The power graph of a group is an undirected graph whose vertex set is the group itself, with two elements being adjacent if one is a power of the other. We analyse the case when the underlying groups of power graphs are cyclic. Another important family of comparability graphs is divisor graphs, which arises from a number-theoretically defined poset, namely the divisibility poset. We consider a subclass of divisor graphs, denoted by D(n), where the vertex set is the set of positive divisors of a natural number n.

We first show that to study the boxicity (cubicity) of the power graph of the cyclic group of order n, it is sufficient to study the boxicity (cubicity) of D(n). We derive estimates, tight up to a factor of 2, for the boxicity and cubicity of D(n). The exact estimates hold good for power graphs of cyclic groups.