3-trees with few vertices of degree 3 in circuit graphs
3-trees with few vertices of degree 3 in circuit graphs
复制标题
DOI：
10.1016/j.disc.2008.01.002
复制
发表时间：
2009-03-06
影响因子：
0.8
通讯作者：
Ota, Katsuhiro
中科院分区：
文献类型：
--
作者：
Nakamoto, Atsuhiro;Oda, Yoshiaki;Ota, Katsuhiro
一个圈图（G，C）是一个2-连通平面图G，它有一个外圈C，使得从每个内顶点v到C有三条不相交的路。在本文中，我们将证明具有n个顶点的电路图具有3-树（即，最大度至多为3的生成树），最多有n-7/3个度为3的顶点。我们对3度顶点数的估计是精确的。利用这一结果，我们证明了在Euler特征数chi >= 0的曲面F（chi）上的n个顶点的3-连通图有至多n/3 + c（chi）个3度顶点的3-树，其中c（chi）是只依赖于F（chi）的常数. (C)2008 Elsevier B. V.保留所有权利。
A circuit graph (G, C) is a 2-connected plane graph G with an outer cycle C such that from each inner vertex v, there are three disjoint paths to C. In this paper, we shall show that a circuit graph with n vertices has a 3-tree (i.e., a spanning tree with maximum degree at most 3) with at most n-7/3 vertices of degree 3. Our estimation for the number of vertices of degree 3 is sharp. Using this result, we prove that a 3-connected graph with n vertices on a surface F(chi) with Euler characteristic chi >= 0 has a 3-tree with at most n/3 + c(chi) vertices of degree 3, where c(chi) is a constant depending only on F(chi). (C) 2008 Elsevier B.V. All rights reserved.