首页 | 本学科首页   官方微博 | 高级检索  
     检索      


3-trees with few vertices of degree 3 in circuit graphs
Authors:Atsuhiro Nakamoto  Yoshiaki Oda
Institution:a Department of Mathematics, Faculty of Education and Human Sciences, Yokohama National University, 79-2 Tokiwadai, Hodogaya-ku, Yokohama 240-8501, Japan
b Department of Mathematics, Faculty of Science and Technology, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223-8522, Japan
Abstract: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 View the MathML source 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χ with Euler characteristic χ≥0 has a 3-tree with at most View the MathML source vertices of degree 3, where cχ is a constant depending only on Fχ.
Keywords:3-connected graph  Circuit graph  3-tree  Surface
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号