Some remarks about leaf roots
Some remarks about leaf roots
复制标题
DOI：
10.1016/j.disc.2006.03.030
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
D. Rautenbach
中科院分区：
文献类型：
--
作者：
D. Rautenbach
Nishimura et al. [On graph powers for leaf-labeled trees，J. Algorithms 42（2002）69-108]定义了一个图G=（VG，EG）的k-叶根为一棵树T=（VT，ET）使得G的顶点恰好是T的叶，并且VG中的两个顶点在G中相邻当且仅当它们在T中的距离至多为k。解决一个问题所提出的Niedermeier [个人通信，2004年5月]，我们给出了一个结构特征的图形，有一个4叶根。此外，我们还证明了具有3-叶子根的图本质上是树，这简化了Dom等人的特征[叶功率问题中的误差补偿（Error compensation in leaf power problems），Apriumica 44（2006）363-381]。（初步版本出现在标题为“叶根问题中的误差补偿”的论文集中：第15届国际算法和计算研讨会论文集（ISAAC 2004），计算机科学讲义，第3341卷，第3341页。389-401）]以及Nishimura等人的相关识别算法[On graph powers for leaf-labeled trees，J. Algorithms 42（2002）69-108]。
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 VGare 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].