論文

査読有り
2015年3月1日

Structural properties of subdivided-line graphs

Journal of Discrete Algorithms
  • Toru Hasunuma

31
開始ページ
69
終了ページ
86
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1016/j.jda.2015.01.008
出版者・発行元
Elsevier

Motivated by self-similar structures of Sierpiński graphs, we newly introduce the sub-divided-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, 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 Sierpiński graphs, and upper bounds on the pagenumbers of Sierpiński 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 Sierpiński graphs, while our proofs are simpler than those for Sierpiński graphs.

リンク情報
DOI
https://doi.org/10.1016/j.jda.2015.01.008
URL
http://dblp.uni-trier.de/db/journals/jda/jda31.html#journals/jda/Hasunuma15

エクスポート
BibTeX RIS