Record Details

Boxicity, Cubicity And Vertex Cover

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Boxicity, Cubicity And Vertex Cover
 
Creator Shah, Chintan D
 
Subject Boxicity
Cubicity
Vortex Cover
Graphs - Boxicity
Graphs - Cubicity
Bipartite Graphs
Interval Graphs
Intersection Graphs
Chromatic Number
Box(G)
Cub(G)
Computer Science
 
Description 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 findingan 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).
 
Contributor Chandran, L Sunil
 
Date 2010-09-28T09:25:49Z
2010-09-28T09:25:49Z
2010-09-28
2008-08
 
Type Thesis
 
Identifier http://hdl.handle.net/2005/890
 
Language en_US
 
Relation G22611