BSCC(4,k)的Hamilton圈分解

doi:10.11896/j.issn.1002-137X.2016.6A.016

计算机科学 ›› 2016, Vol. 43 ›› Issue (Z6): 73-76.doi: 10.11896/j.issn.1002-137X.2016.6A.016

BSCC(4,k)的Hamilton圈分解

胡艳红,师海忠

西北师范大学数学与统计学院兰州730070,西北师范大学数学与统计学院兰州730070

出版日期:2018-12-01 发布日期:2018-12-01

Hamilton Descomposition of BSCC(4,k)

HU Yan-hong and SHI Hai-zhong

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。

关键词: 冒泡排序连通圈网络,Hamilton圈,猜想,完美对集,Cayley图

Abstract: Bubble-sort connected cycle is an important class of interconnection network.Shi Hai-zhong conjectured that BSCC(n)(n≥4) is a union of edge disjoint a Hamiltonian cycle and a perfect matching.Denoting BSCC(n) as BSCC(n,0),we studied the new network BSCC(4,1) by using a triangle to replace per vertex of BSCC(4,0),and BSCC(4,2) was gotten by using a triangle to replace every vertex of BSCC(4,1).In the similar way,the new network was gotten by using a triangle to replace every vertex for k times.Shi Hai-zhong raised the conjecture 2 further more:BSCC(n,k) is a union of edge disjoint a Hamiltonian cycle and a perfect matching.In this paper,we proved that BSCC(4,k) is a union of edge disjoint a Hamiltonian cycle and a perfect matching.

Key words: (n,k)-Bubble-sort connected cycle,Hamilton cycle,Conjecture,Perfect matching,Cayley graphs

胡艳红,师海忠. BSCC(4,k)的Hamilton圈分解[J]. 计算机科学, 2016, 43(Z6): 73-76. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.016

HU Yan-hong and SHI Hai-zhong. Hamilton Descomposition of BSCC(4,k)[J]. Computer Science, 2016, 43(Z6): 73-76. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.016

参考文献

[1] Lakshmivarahan S,jwo ang J S,Dhall S K.Symmetry in interconnection netwerks based on Cayley graphs of permutation groups:A survey[J].Parallel Computing,1993,19(4):361-407
[2] 徐俊明.组合网络理论[M].北京:科学出版社,2007:198-234
[3] 高随祥.图论与网络流理论[M].北京:高等教育出版社,2009:1-52
[4] 师海忠.互连网络的代数环模型[D].北京:中国科学院数学与系统科学研究院应用数学研究所,1998
[5] Shi Hai-zhong,Niu Pan-feng.Hamiltonian deconposition of someintercoonection networks[C]∥Du Ding-zhu.Proceed of the 3th Aunnal International Conference on Combinatorial Optimization and Applications.Huang Shan,China:Springer,June 2009:231-237
[6] Bondy J A,Marty U S R.Graph Theory[M].London:Sprin-ger,2008
[7] Akers S B,Krishnamurthy B.A group-theoretic model for symmetric interconnection network[J].IEEE Transaction on Computers,1989,38(4):555-565
[8] 师海忠,牛攀峰.冒泡排序网络的控制数[J].甘肃科学学报,2010,2(3):32-35
[9] Biggs N.Algebraic Graph theory(second edition)[M].Cam-bridge University Press,1993
[10] Shi Hai-zhong,Shi Yue.Cell-breeding graph model for interconnection networks.http://vdisk.weibo.com/s/dlizJyfesb05y
[11] 师海忠,师越.关于互连网络群论模型的一簇猜想[J].计算机科学,2015,2(11A):245-246,9
[12] Shi Hai-zhong,Shi Yue.A new model for interconnection network:k-hierarchical ring and r-layer graph network.http://vdisk.weibo.com/s/dlizJyferZ-Zl
[13] Shi Hai-zhong,Shi Yue.A hierarchical Ring Group-TheoreticModel for Interconnection Networks.http://vdisk.weibo.com/s/dlizJyfeBX-2J
[14] Ohring S R,Sarkar F,Hohndel D H.Cayley graph connected cycles:A new class of fixed-degree Interconnection networks[C]∥Proceeding of the 28th Annual Hawaii International Conference on System Science.1995:479-488
[15] 师海忠.正则图连通圈:多种互连网络的统一模型[C]∥中国运筹学会第十一届学术交流会论文集.北京,2010:202-208

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

BSCC(4,k)的Hamilton圈分解

Hamilton Descomposition of BSCC(4,k)

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0