Title of article :
3-trees with few vertices of degree 3 in circuit graphs
Author/Authors :
Nakamoto، نويسنده , , Atsuhiro and Oda، نويسنده , , Yoshiaki and Ota، نويسنده , , Katsuhiro، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
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 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 χ with Euler characteristic χ ≥ 0 has a 3-tree with at most n 3 + c χ vertices of degree 3, where c χ is a constant depending only on F χ .
Keywords :
3-tree , surface , 3-connected graph , Circuit graph
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics