设图,G,为,2n,阶,(n-2)-,正则二部图.构造了图,G,的一个基本圈基并且证明了此圈基就是图,G,的一个最小基本圈基,同时还确定了任意最小基本圈基对应的生成树的结构
何常香
,
刘伟龙
. 2n阶(n-2)-正则二部图的最小基本圈基[J]. 华东师范大学学报(自然科学版), 2016
, 2016(2)
: 56
-61
.
DOI: 2016.02.008
Let G be an (n-2)- regular bipartite graph with order 2n. In this paper, we constructed a fundamental cycle basis of G and proved this basis is a minimum fundamental cycle basis. For any minimum fundamental cycle basis, we also determined the structure of the spanning tree corresponding to it.
[1] LIEBCHEN C, RIZZI R. Classes of cycle bases[J].Discrete Appl Math, 2007, 155(3): 337-355.
[2]HORTON J D. A polynomial-time algorithm to find the shortest cyclebasis of a graph[J]. SIAM J Computing, 1987, 16: 359-366.
[3]BRADSHAW Z, JARADAT M M M. Minimum cycle bases for direct productsof\,K_{2]\,with complete graphs[J]. Australas J Combin, 2009, 43:127-131.
[4]HAMMACK R. Minimum cycle bases of direct products of complete graphs[J]. Inform Process Lett, 2007, 102(5): 214-218.
[5]STADLER P. Minimum cycle bases of Halin graphs[J]. J Graph Theory, 2003, 43(2): 150-155.
[6]KAVITHA T, LIEBCHEN C, MEHLHORN K, et al. Cycle bases in graphs characterization, algorithms, complexity, and applications[J]. Comput Sci Rev, 2009, 3(4): 199-243.
[7]GHAREGHANI N, KHOSROVSHAHI G B. Minimum cycle basis of direct product of\,K_{2]\times K_{n]\,[J]. Linear Algebra Appl, 2014,458: 671-678.
[8]BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York:Macmilan Ltd Press, 1976.
[9]LU M. Spectral radius and Hamiltonian graphs[J]. Linear Algebra Appl, 2012, 437: 1670-1674.