The hamiltonicity and path -coloring of Sierpi艅ski-like graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Bing Xue^a ; Liancui Zuo^b ; ^{zuolc@vip.sina.com} ; ^{zuolc@yahoo.com.cn} ; ^{lczuo@mail.tjnu.edu.cn} ; Guojun Li^a
• 关键词：Hamiltonicity ; Path t-coloring ; Vertex linear arboricity ; Sierpi艅ski graph ; Matching
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：August, 2012
• 卷：160
• 期：12
• 页码：1822-1836
• 文件大小：445 K

摘要

A mapping from to is called a path -coloring of a graph if each , for , is a linear forest. The vertex linear arboricity of a graph , denoted by , is the minimum for which has a path -coloring. Graphs are obtained from the Sierpi艅ski graphs by contracting all edges that lie in no induced . In this paper, the hamiltonicity and path -coloring of Sierpi艅ski-like graphs , , and graphs are studied. In particular, it is obtained that for . Moreover, the numbers of edge disjoint Hamiltonian paths and Hamiltonian cycles in , and are completely determined, respectively.