Boxicity of leaf powers
From MaRDI portal
Publication:659669
DOI10.1007/S00373-010-0962-5zbMATH Open1234.05169arXiv0902.3551OpenAlexW2102429849MaRDI QIDQ659669FDOQ659669
Authors: L. Sunil Chandran, Mathew C. Francis, Rogers Mathew 
Publication date: 24 January 2012
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Abstract: The boxicity of a graph G, denoted as box(G) is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are a subclass of strongly chordal graphs and are used in the construction of phylogenetic trees in evolutionary biology. We show that for a k-leaf power G, box(G)leq k-1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k-1. This result implies that there exists strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.
Full work available at URL: https://arxiv.org/abs/0902.3551
Recommendations
Applications of graph theory (05C90) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Representation of a finite graph by a set of intervals on the real line
- Characterizations of strongly chordal graphs
- Interval representations of planar graphs
- Boxicity and treewidth
- Title not available (Why is that?)
- Boxicity of series-parallel graphs
- Title not available (Why is that?)
- On graph powers for leaf-labeled trees
- On (k,ℓ)-Leaf Powers
- Structure and linear-time recognition of 4-leaf powers
- Structure and linear time recognition of 3-leaf powers
- Boxicity and maximum degree
- Computing the boxicity of a graph by covering its complement by cointerval graphs
- Boxicity of circular arc graphs
- Geometric representation of graphs in low dimension using axis parallel boxes
- Strong clique trees, neighborhood trees, and strongly chordal graphs
- Title not available (Why is that?)
- Strictly chordal graphs are leaf powers
- Boxicity of Halin graphs
- A characterization of strongly chordal graphs
- Closest 4-leaf power is fixed-parameter tractable
- Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs
Cited In (3)
This page was built for publication: Boxicity of leaf powers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659669)
