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.
HE Chang-Xiang
,
LIU Wei-Long
. Minimum fundamental cycle basis of (n-2)-regular bipartite graphs with order 2n[J]. Journal of East China Normal University(Natural Science), 2016
, 2016(2)
: 56
-61
.
DOI: 2016.02.008
[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.