Cubicity of interval graphs and the claw number

✍ Scribed by Abhijin Adiga; L. Sunil Chandran

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 119 KB
• Volume: 65
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20483

✦ Synopsis

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 I 1 ×I 2 ו • •×I b , where each I i is a closed interval of unit length on the real line. The cubicity 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 (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 (G) . In this article, we show that for an interval graph G log 2 (G) ≤ cub(G) ≤ log 2 (G) +2. It is not clear whether the upper bound of log 2 (G) +2 is tight: till now we are unable to find any interval graph with cub(G)> log 2 (G) . We also show