期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

The Existence of Even Regular Factors of Regular Graphs on the Number of Cut Edges

The Existence of Even Regular Factors of Regular Graphs on the Number of Cut Edges
原文传递
导出
摘要 For any even integer k and any integer i, we prove that a （kr ＋i）-regular multigraph contains a k-factor if it contains no more than kr - 3k/2＋ i ＋ 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs. For any even integer k and any integer i, we prove that a （kr ＋i）-regular multigraph contains a k-factor if it contains no more than kr - 3k/2＋ i ＋ 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs.
作者 Hong Bing FAN Gui Zhen LIU Ji Ping LIU He Ping LONG
机构地区 Department of Computer Science School of Mathematics Department of Computer Science
出处 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2010年第12期2305-2312,共8页 数学学报（英文版）
基金 Supported by Natural Sciences and Engineering Research Council of Canada NNSF (Grant No. 10871119) RSDP (Grant No. 200804220001) of China
关键词 Regular graph FACTOR cut edge Regular graph, factor, cut edge
分类号 O157.5 [理学—基础数学] TQ051.84 [化学工程]
  • 相关文献

参考文献1

  • 1FAN Hongbing, LIU Guizhen & LIU Jiping Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, ON., N2L 3C5 Canada,School of Mathematics and System Science, Shandong University, Jinan 250100, China,Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, AB., T1K 3M4, Canada.Minimal regular 2-graphs and applications[J].Science China Mathematics,2006,49(2):158-172. 被引量：1

二级参考文献13

  • 1[1]Bondy,J.A.,Murty,U.R.S.,Graph Theory with Applications,London:MacMillan Press,1976.
  • 2[2]Berge,C.,Graphs and Hypergraphs,New York:Elsevier Science Publication Company,Inc.,1985.
  • 3[3]Fan,H.,Liu,J.,Wu,Y.L.et al.,Reduction design for generic universal switch blocks,ACM Transactions on Design Automation of Electronic Systems (TODAES),2002,7(4):526-546.
  • 4[4]Higman,G.,Ordering by divisibility in abstract algebras,Proc.London Math.Soc.,1952,2 (3):326-336.
  • 5[5]Contejean,E.,Devie,H.,An efficient incremental algorithm for solving systems of linear Diophantine equations,Inform.Comput.,1994,113(1):143-172.
  • 6[6]Tutte,W.T.,The factorization of linear graphs,J.London Math.Soc.,1947,22(1):107-111.
  • 7[7]Petersen,J.,Die theorie der regularen graphs,Acta Math.,1891,15(2):193-220.
  • 8[8]Akiyama,J.,Kano,M.,Factors and Factorization of Graphs-A survey,J.Graph Theory,1985,9(1):67-86.
  • 9[9]Fan,H.,Liu,J.,Wu,Y.L.,General models and a reduction design technique for FPGA switch box designs,IEEE Transactions on Computers,2003,52(1):.21-30.
  • 10[10]Pottier,L.,Minimal solutions of linear Diophantine systems:Bounds and algorithms,in Proceedings of the 4th International Conference on Rewriting Techniques aud Applications,Lecture Notes in Computer Science (ed.Book,R.V.),Berlin:Springer,1991,488:162-173.
Acta Mathematica Sinica,English Series
2010年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部