Journal of East China Normal University(Natural Science) >

2016 , Vol. 2016 >Issue 2: 56 - 61

DOI: https://doi.org/2016.02.008

Article

Minimum fundamental cycle basis of (n-2)-regular bipartite graphs with order 2n

  • HE Chang-Xiang ,
  • LIU Wei-Long
Expand

Received date: 2015-04-24

  Online published: 2016-07-25

Fold

Abstract

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.

Key words： regular bipartite graph; cycle basis of graph; minimum cycle basis; minimum fundamental cycle basis

Cite this article

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

References

[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.
Options
Outlines

/

〈 〉