The P3 Intersection Graph

We define a new graph operator called the P3 intersection graph, P3(G)- the intersection graph of all induced 3-paths in G. A characterization of graphs G for which P-3 (G) is bipartite is given . Forbidden subgraph characterization for P3 (G) having properties of being chordal , H-free, complete are also obtained . For integers a and b with a > 1 and b > a - 1, it is shown that there exists a graph G such that X(G) = a, X(P3( G)) = b, where X is the chromatic number of G. For the domination number -y(G), we construct graphs G such that -y(G) = a and -y (P3(G)) = b for any two positive numbers a > 1 and b. Similar construction for the independence number and radius, diameter relations are also discussed.

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.

REPRESENTING A CUBIC GRAPH AS THE INTERSECTION GRAPH OF AXIS-PARALLEL BOXES IN THREE DIMENSIONS

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes touch just at their boundaries.

Studies on some graph operators and related topics

Department of Mathematics, Cochin University of Science and Technology

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Finding a Box Representation for a Graph in $O(n^2\Delta^2\ln n)$ time

An axis-parallel box in $b$-dimensional space is a Cartesian product $R_1 \times R_2 \times \cdots \times R_b$ where $R_i$ (for $1 \leq i \leq b$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its boxicity is the minimum dimension $b$, such that $G$ is representable as the intersection graph of (axis-parallel) boxes in $b$-dimensional space. The concept of boxicity finds application in various areas of research like ecology, operation research etc. Chandran, Francis and Sivadasan gave an $O(\Delta n^2 \ln^2 n)$ randomized algorithm to construct a box representation for any graph $G$ on $n$ vertices in $\lceil (\Delta + 2)\ln n \rceil$ dimensions, where $\Delta$ is the maximum degree of the graph. They also came up with a deterministic algorithm that runs in $O(n^4 \Delta )$ time. Here, we present an $O(n^2 \Delta^2 \ln n)$ deterministic algorithm that constructs the box representation for any graph in $\lceil (\Delta + 2)\ln n \rceil$ dimensions.

On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k, where each R-i is a closed interval on the real line of the form [a(j), a(i), + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for graph G, cub(G) <= left perpendicular2n/3right perpendicular. Recently it has been shown that for a graph G, cub(G) >= 4(Delta + 1) In n, where n and Delta are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G = (A boolean OR B, E) with |A| = n(1), |B| = n2, n(1) <= n(2), and Delta' = min {Delta(A),Delta(B)}, where Delta(A) = max(a is an element of A)d(a) and Delta(B) = max(b is an element of B) d(b), d(a) and d(b) being the degree of a and b in G, respectively , cub(G) <= 2(Delta' + 2) bar left rightln n(2)bar left arrow. We also give an efficient randomized algorithm to construct the cube representation of G in 3 (Delta' + 2) bar right arrowIn n(2)bar left arrow dimension. The reader may note that in general Delta' can be much smaller than Delta.

An upper bound for Cubicity in terms of Boxicity

An axis-parallel b-dimensional box is a Cartesian product R-1 x R-2 x ... x R-b where each R-i (for 1 <= i <= b) is a closed interval of the form [a(i), b(i)] on the real line. The boxicity of any graph G, box(G) is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R-1 x R-2 x ... x R-b, where each R-i (for 1 <= i <= b) is a closed interval of the form [a(i), a(i) + 1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by cub(G)). In this paper we prove that cub(G) <= inverted right perpendicularlog(2) ninverted left perpendicular box(G), where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below: 1. Planar graphs have cubicity at most 3inverted right perpendicularlog(2) ninvereted left perpendicular.2. Outer planar graphs have cubicity at most 2inverted right perpendicularlog(2) ninverted left perpendicular.3. Any graph of treewidth tw has cubicity at most (tw + 2) inverted right perpendicularlog(2) ninverted left perpendicular. Thus, chordal graphs have cubicity at most (omega + 1) inverted right erpendicularlog(2) ninverted left perpendicular and circular arc graphs have cubicity at most (2 omega + 1)inverted right perpendicularlog(2) ninverted left perpendicular, where omega is the clique number.

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G,denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R-1 x R-2 x ... x R-k where each Ri is a closed interval on the real line of the form [a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G) <= t + inverted right perpendicularlog(n - t)inverted left perpendicular - 1 and box(G) <= left perpendiculart/2right perpendicular + 1, where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, box(G) <= left perpendicularn/2right perpendicular and cub(G) <= inverted right perpendicular2n/3inverted left perpendicular, where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then box(G) <= inverted right perpendicularn/4inverted left perpendicular and this bound is tight. We also show that if G is a bipartite graph then cub(G) <= n/2 + inverted right perpendicularlog n inverted left perpendicular - 1. We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to n/4. Interestingly, if boxicity is very close to n/2, then chromatic number also has to be very high. In particular, we show that if box(G) = n/2 - s, s >= 0, then chi (G) >= n/2s+2, where chi (G) is the chromatic number of G.

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K-4, then box(G) = 2. In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then box(G) = 2 unless G is isomorphic to K4 (in which case its boxicity is 1).

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Boxicity and maximum degree

A d-dimensional box is a Cartesian product of d closed intervals on the real line. The boxicity of a graph is the minimum dimension d such that it is representable as the intersection graph of d-dimensional boxes. We give a short constructive proof that every graph with maximum degree D has boxicity at most 2D2. We also conjecture that the best upper bound is linear in D.

Boxicity and cubicity of asteroidal triple free graphs

The boxicity of a graph G, denoted box(G), is the least integer d such that G is the intersection graph of a family of d-dimensional (axis-parallel) boxes. The cubicity, denoted cub(G), is the least dsuch that G is the intersection graph of a family of d-dimensional unit cubes. An independent set of three vertices is an asteroidal triple if any two are joined by a path avoiding the neighbourhood of the third. A graph is asteroidal triple free (AT-free) if it has no asteroidal triple. The claw number psi(G) is the number of edges in the largest star that is an induced subgraph of G. For an AT-free graph G with chromatic number chi(G) and claw number psi(G), we show that box(G) <= chi(C) and that this bound is sharp. We also show that cub(G) <= box(G)([log(2) psi(G)] + 2) <= chi(G)([log(2) psi(G)] + 2). If G is an AT-free graph having girth at least 5, then box(G) <= 2, and therefore cub(G) <= 2 [log(2) psi(G)] + 4. (c) 2010 Elsevier B.V. All rights reserved.

Cubicity of Interval Graphs and the Claw Number

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b-dimensional cube is a Cartesian product l(1) x l(2) x ... x l(b), where each l(i) is a closed interval of unit length on the real line. The cub/city of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b-dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line-i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number psi(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least log(2) psi(G)]. In this article, we show that for an interval graph G log(2) psi(G)-]<= cub(G)<=log(2) psi(G)]+2. It is not clear whether the upper bound of log(2) psi(G)]+2 is tight: till now we are unable to find any interval graph with cub(G)> (log(2)psi(G)]. We also show that for an interval graph G, cub(G) <= log(2) alpha], where alpha is the independence number of G. Therefore, in the special case of psi(G)=alpha, cub(G) is exactly log(2) alpha(2)]. The concept of cubicity can be generalized by considering boxes instead of cubes. A b-dimensional box is a Cartesian product l(1) x l(2) x ... x l(b), where each I is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k-dimensional boxes. It is clear that box(G)<= cub(G). From the above result, it follows that for any graph G, cub(G) <= box(G)log(2) alpha]. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323-333, 2010

Boxicity of Leaf Powers

The boxicity of a graph G, denoted as boxi(G), is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are used in the construction of phylogenetic trees in evolutionary biology and have been studied in many recent papers. We show that for a k-leaf power G, boxi(G) a parts per thousand currency sign k-1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k-1. This result implies that there exist strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.