論文

査読有り
2013年

Structural properties of subdivided-line graphs

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • Toru Hasunuma

8288
開始ページ
216
終了ページ
229
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-642-45278-9_19
出版者・発行元
Springer

Motivated by self-similar structures of Sierpiński 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 Sierpiński 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 Sierpiński graphs, while our proofs are simpler than those for Sierpiński graphs. © 2013 Springer-Verlag.

リンク情報
DOI
https://doi.org/10.1007/978-3-642-45278-9_19
URL
http://dblp.uni-trier.de/db/conf/iwoca/iwoca2013.html#conf/iwoca/Hasunuma13

エクスポート
BibTeX RIS