Structural properties of subdivided-line graphs
Structural properties of subdivided-line graphs
复制标题
DOI：
10.1016/j.jda.2015.01.008
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Toru Hasunuma
中科院分区：
文献类型：
--
作者：
Toru Hasunuma
受Sierpienski图的自相似结构的启发，引入了细分线图运算Γ，定义了图G的n-迭代细分线图Γ n（G）.然后，我们研究了细分线图的结构性质，如边不相交的汉密尔顿圈，汉密尔顿连通性，枢纽集，连通控制集，独立的生成树，完全独立的生成树，和书嵌入，可以应用于互联网络上的问题。根据我们的结果，得到了Sierpiński图中边不相交的汉密尔顿圈的最大数量、中心集的最小基数、连通控制集的最小基数、Sierpiński图中独立生成树的最大数量和完全独立生成树的最大数量，以及Sierpiński图最多为最优值两倍的页码的上界作为推论。特别地，我们对迭代细分线图上边不交的汉密尔顿圈和枢纽集的结果是Sierpienski图上已有结果的推广，而我们的证明比Sierpienski图的证明简单.
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.