Some remarks about leaf roots |
| |
Authors: | Dieter Rautenbach |
| |
Institution: | Forschungsinstitut für Diskrete Mathematik, Universität Bonn, Lennéstr. 2, D-53113 Bonn, Germany |
| |
Abstract: | Nishimura et al. On graph powers for leaf-labeled trees, J. Algorithms 42 (2002) 69-108] define a k-leaf root of a graph G=(VG,EG) as a tree T=(VT,ET) such that the vertices of G are exactly the leaves of T and two vertices in VG are adjacent in G if and only if their distance in T is at most k. Solving a problem posed by Niedermeier Personal communication, May 2004] we give a structural characterization of the graphs that have a 4-leaf root. Furthermore, we show that the graphs that have a 3-leaf root are essentially the trees, which simplifies a characterization due to Dom et al. Error compensation in leaf power problems, Algorithmica 44 (2006) 363-381. (A preliminary version appeared under the title “Error compensation in leaf root problems”, in: Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Computer Science, vol. 3341, pp. 389-401)] and also a related recognition algorithm due to Nishimura et al. On graph powers for leaf-labeled trees, J. Algorithms 42 (2002) 69-108]. |
| |
Keywords: | Leaf root Forbidden induced subgraph |
本文献已被 ScienceDirect 等数据库收录! |
|