Boxicity of Line Graphs

2010/09/22 by L. Sunil Chandran, Chandran, L. Sunil, Rogers Mathew +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1009.4471

Abstract

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Δ(\lceil log₂(log₂(Δ)) \rceil + 3) + 1, where Δdenotes the maximum degree of G. Since Δ<= 2(χ- 1), for any line graph G with chromatic number χ, box(G) = O(χlog₂(log₂(χ))). For the d-dimensional hypercube H_d, we prove that box(H_d) >= (\lceil log₂(log₂(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).

Cited by

• A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs

Related

• On the Boxicity of Line Graphs and of Their Complements
• Boxicity and Maximum degree
• On the Boxicity and Cubicity of Hypercubes
• An upper bound for Cubicity in terms of Boxicity
• Upper bound on cubicity in terms of boxicity for graphs of low chromatic number