The hamiltonicity and path tt-coloring of Sierpiński-like graphs

A mapping ϕϕ from V(G)V(G) to {1,2,…,t}{1,2,…,t} is called a path  tt-coloring   of a graph GG if each G[ϕ−1(i)]G[ϕ−1(i)], for 1≤i≤t1≤i≤t, is a linear forest. The vertex linear arboricity of a graph GG, denoted by vla(G), is the minimum tt for which GG has a path tt-coloring. Graphs S[n,k]S[n,k] are obtained from the Sierpiński graphs S(n,k)S(n,k) by contracting all edges that lie in no induced KkKk. In this paper, the hamiltonicity and path tt-coloring of Sierpiński-like graphs S(n,k)S(n,k), S+(n,k)S+(n,k), S++(n,k)S++(n,k) and graphs S[n,k]S[n,k] are studied. In particular, it is obtained that vla(S(n,k))=vla(S[n,k])=⌈k/2⌉ for k≥2k≥2. Moreover, the numbers of edge disjoint Hamiltonian paths and Hamiltonian cycles in S(n,k)S(n,k), S+(n,k)S+(n,k) and S++(n,k)S++(n,k) are completely determined, respectively.