etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >
Please use this identifier to cite or link to this item:
|Title: ||Boxicity, Cubicity And Vertex Cover|
|Authors: ||Shah, Chintan D|
|Advisors: ||Chandran, L Sunil|
Graphs - Boxicity
Graphs - Cubicity
|Submitted Date: ||Aug-2008|
|Series/Report no.: ||G22611|
|Abstract: ||The boxicity of a graph G, denoted as box(G), is the minimum dimension d for which each vertex of G can be mapped to a d-dimensional axis-parallel box in Rd such that two boxes intersect if and only if the corresponding vertices of G are adjacent. An axis-parallel box is a generalized rectangle with sides parallel to the coordinate axes. If additionally, we restrict all sides of the rectangle to be of unit length, the new parameter so obtained is called the cubicity of the graph G, denoted by cub(G).
F.S. Roberts had shown that for a graph G with n vertices, box(G) ≤ and cub(G) ≤ . A minimum vertex cover of a graph G is a minimum cardinality subset S of the vertex set of G such that each edge of G has at least one endpoint in S. We show that box(G) ≤ +1 and cub(G)≤ t+ ⌈log2(n −t)⌉−1 where t is the cardinality of a minimum vertex cover. Both these bounds are tight.
For a bipartite graph G, we show that box(G) ≤ and this bound is tight. We observe that there exist graphs of very high boxicity but with very low chromatic num-ber. For example, there exist bipartite (2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then the chromatic number also has to be very high. In particular, we show that if box(G) = −s, s ≥ 02, then x(G) ≥ where X(G) is the chromatic number of G.
We also discuss some known techniques for ﬁndingan upper boundon the boxicityof a graph -representing the graph as the intersection of graphs with boxicity 1 (boxicity 1 graphs are known as interval graphs) and covering the complement of the graph by co-interval graphs (a co-interval graph is the complement of an interval graph).|
|Appears in Collections:||Computer Science and Automation (csa)|
Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.