06065744

j

06065744 Xue, Bing Zuo, Liancui Li, Guojun The hamiltonicity and path $t$-coloring of Sierpi\'nski-like graphs. Discrete Appl. Math. 160, No. 12, 1822-1836 (2012). 2012 Elsevier Science B.V. (North-Holland), Amsterdam EN hamiltonicity path $t$-coloring vertex linear arboricity Sierpi\'nski graph matching

doi:10.1016/j.dam.2012.03.022

Summary: A mapping $\phi $ from $V(G)$ to $\{1,2,\ldots ,t\}$ is called a patht-coloring of a graph $G$ if each $G[\phi ^{ - 1}(i)]$, for $1\le i\le t$, is a linear forest. The vertex linear arboricity of a graph $G$, denoted by vla$(G)$, is the minimum $t$ for which $G$ has a path $t$-coloring. Graphs $S[n,k]$ are obtained from the Sierpi\'nski graphs $S(n,k)$ by contracting all edges that lie in no induced $K_{k}$. In this paper, the hamiltonicity and path $t$-coloring of Sierpi\'nski-like graphs $S(n,k), S^{+}$(n,k), $S^{++}$(n,k) and graphs $S[n,k]$ are studied. In particular, it is obtained that vla$(S(n,k))=\text{vla}(S[n,k]) = \lceil k/2 \rceil$ for $k \ge 2$. Moreover, the numbers of edge disjoint Hamiltonian paths and Hamiltonian cycles in $S(n,k)$, $S^{+}(n,k)$ and $S^{++}(n,k)$ are completely determined, respectively.