Boxicity of Halin Graphs

Details Boxicity of Halin Graphs Boxicity of Halin Graphs

2007-11-09

arxiv.org/abs/0711.1417v1

Mathematics

Combinatorics

9 pages

Scientific paper

A k-dimensional box is the Cartesian product R_1 x R_2 x ... x R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K_4, then box(G)=2. In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then box(G)=2 unless G is isomorphic to K_4 (in which case its boxicity is 1).

Affiliated with

Also associated with

No associations

Rating

Boxicity of Halin 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 Halin Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity of Halin Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-702240