کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423548 | 1342419 | 2011 | 9 صفحه PDF | دانلود رایگان |
The 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 Rk. In this paper we show that for a line graph G of a multigraph, box(G)â¤2Î(G)(âlog2log2Î(G)â+3)+1, where Î(G) denotes the maximum degree of G. Since G is a line graph, Î(G)â¤2(Ï(G)â1), where Ï(G) denotes the chromatic number of G, and therefore, box(G)=O(Ï(G)log2log2(Ï(G))). For the d-dimensional hypercube Qd, we prove that box(Qd)â¥12(âlog2log2dâ+1). The question of finding a nontrivial lower bound for box(Qd) was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795-5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).
⺠Boxicity of a line graph G is O(D(loglogD)), where D denotes the maximum degree of G. ⺠Boxicity of a line graph G is O(k(loglogk)), where k denotes the chromatic number of G. ⺠Boxicity of the d-dimensional hypercube is at least (1/2)(âloglogdâ+1).
Journal: Discrete Mathematics - Volume 311, Issue 21, 6 November 2011, Pages 2359-2367