Boxicity of Line Graphs

Details Boxicity of Line Graphs Boxicity of Line Graphs

2010-09-22

arxiv.org/abs/1009.4471v1

Mathematics

Combinatorics

14 pages

Scientific paper

Boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper, we show that for a line graph G of a multigraph, box(G) <= 2\Delta(\lceil log_2(log_2(\Delta)) \rceil + 3) + 1, where \Delta denotes the maximum degree of G. Since \Delta <= 2(\chi - 1), for any line graph G with chromatic number \chi, box(G) = O(\chi log_2(log_2(\chi))). For the d-dimensional hypercube H_d, we prove that box(H_d) >= (\lceil log_2(log_2(d)) \rceil + 1)/2. The question of finding a non-trivial lower bound for box(H_d) was left open by Chandran and Sivadasan in [L. Sunil Chandran and Naveen Sivadasan. The cubicity of Hypercube Graphs. Discrete Mathematics, 308(23):5795-5800, 2008]. The above results are consequences of bounds that we obtain for the boxicity of fully subdivided graphs (a graph which can be obtained by subdividing every edge of a graph exactly once).

Affiliated with

Also associated with

No associations

Rating

Boxicity of Line Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boxicity of Line Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity of Line Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-338035