Mathematics – Combinatorics
Scientific paper
2006-10-08
Mathematics
Combinatorics
4 pages
Scientific paper
An axis-parallel $d$--dimensional box is a Cartesian product $R_1 \times R_2 \times ... \times R_d$ where $R_i$ (for $1 \le i \le d$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its \emph{boxicity} $\boxi(G)$ is the minimum dimension $d$, such that $G$ is representable as the intersection graph of (axis--parallel) boxes in $d$--dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research etc. We show that for any graph $G$ with maximum degree $\Delta$, $\boxi(G) \le 2 \Delta^2 + 2$. That the bound does not depend on the number of vertices is a bit surprising considering the fact that there are highly connected bounded degree graphs such as expander graphs. Our proof is very short and constructive. We conjecture that $\boxi(G)$ is $O(\Delta)$.
Chandran Sunil L.
Francis Mathew C.
Sivadasan Naveen
No associations
LandOfFree
Boxicity and Maximum degree 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 and Maximum degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity and Maximum degree will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-518724