华东师范大学学报（自然科学版） >

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

DOI: https://doi.org/2016.02.008

数学

2n阶(n-2)-正则二部图的最小基本圈基

  • 何常香 ,
  • 刘伟龙
展开
  • 上海理工大学~~理学院, 上海200093)
何常香, 女, 副教授, 硕士生导师, 研究方向为代数图论. E-mail: changxiang-he@163.com.

收稿日期: 2015-04-24

  网络出版日期: 2016-07-25

基金资助

国家自然科学基金(11201303, 11301340);
上海市自然科学基金(12ZR1420300)

收起

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

摘要

设图,G,为,2n,阶,(n-2)-,正则二部图.构造了图,G,的一个基本圈基并且证明了此圈基就是图,G,的一个最小基本圈基,同时还确定了任意最小基本圈基对应的生成树的结构

关键词： 正则二部图; 图的圈基; 最小圈基; 最小基本圈基

本文引用格式

何常香 , 刘伟龙 . 2n阶(n-2)-正则二部图的最小基本圈基[J]. 华东师范大学学报（自然科学版）, 2016 , 2016(2) : 56 -61 . DOI: 2016.02.008

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

参考文献

[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
文章导航

/

〈 〉