Motivated by self-similar structures of Sierpinski graphs, we newly introduce the subdivided-line graph operation Γ and define the n-iterated subdivided-line graph Γ~n(G) of a graph G. We then study structural properties of subdivided-line graphs such as edge-disjoint Hamilton cycles, hub sets, connected dominating sets, and completely independent spanning trees which can be applied to problems on interconnection networks. From our results, the maximum number of edge-disjoint Hamilton cycles, the minimum cardinality of a hub set, the minimum cardinality of a connected dominating set, and the maximum number of completely independent spanning trees in Sierpiriski graphs are obtained as corollaries. In particular, our results for edge-disjoint Hamilton cycles and hub sets on iterated subdivided-line graphs are generalizations of the previously known results on Sierpinski graphs, while our proofs are simpler than those for Sierpinski graphs.
展开▼
