On the Cubicity of Interval Graphs |
| |
Authors: | L Sunil Chandran Mathew C Francis Naveen Sivadasan |
| |
Institution: | (1) Department of Computer Science and Automation, Indian Institute of Science, Bangalore, 560012, India;(2) Advanced Technology Centre, TCS, Deccan Park, Madhapur, Hyderabad, 500 081, India |
| |
Abstract: | A k-cube (or “a unit cube in k dimensions”) is defined as the Cartesian product where R
i
(for 1 ≤ i ≤ k) is an interval of the form a
i
, a
i
+ 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub(G), is defined as the minimum dimension k such that G has a k-cube representation. 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. We show that for any interval graph G with maximum degree Δ, . This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity
is equal to . |
| |
Keywords: | Cubicity Maximum degree Interval graph |
本文献已被 SpringerLink 等数据库收录! |
|