Structural properties of subdivided-line graphs

Motivated by self-similar structures of Sierpinski graphs, we newly introduce the sub-divided-line graph operation Gamma and define the n-iterated subdivided-line graph Gamma(n)(G) of a graph G. We then study structural properties of subdivided-line graphs such as edge-disjoint Hamilton cycles, hamiltonian-connectivity, hub sets, connected dominating sets, independent spanning trees, completely independent spanning trees, and book-embeddings 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, the maximum number of independent spanning trees and the maximum number of completely independent spanning trees in Sierpinski graphs, and upper bounds on the pagenumbers of Sierpinski graphs which are at most two times the optimums 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. (c) 2015 Elsevier B.V. All rights reserved.