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

无三角形的C(l,k)的超欧拉性 被引量：5

On the Supereulerian Nature of Trlangle-Free C(l,k)
原文传递
导出
摘要 引入了C(l,k)图类的概念:对于整数k≥0及整数l>0,用C(l,k)表示一类n阶2-边连通图.图G∈C(l,k)当且仅当对于任意的边割集SE(G),|S|≤3,使G-S的任一分支至少有(n-k)/l个顶点.证明了:若无三角形的图G∈C(6,5),则G是超欧拉的当且仅当G不能收缩为几个特殊的图. Graph G is supereulerian, if G has a spanning eulerian subgraph. Let l〉 0 and k ≥0 be two integers. Graph G ∈C（l, k） if and only if G with order n is 2-edge-connected and for every bond S ∩→ E（G） with ｜ S ｜ 3, each component of G-S has order at least （n-k）/l. It is proved that ifG G∈（6, 5） and Gis triangle-free, then G is supereulerian if and only if G can not be contracted to some well classified special graphs.
作者 李霄民 李盛瑜
机构地区 重庆工商大学数学与统计学院 重庆工商大学计算机与信息工程学院
出处 《西南大学学报（自然科学版）》 CAS CSCD 北大核心 2008年第12期9-12,共4页 Journal of Southwest University(Natural Science Edition)
基金 重庆市自然科学基金资助项目(CSTC 2007BA2024) 重庆市教委资助项目(KJ0707010)
关键词 超欧拉图 可折叠子图 无三角形 简化图 supereulerian graphs collapsible graphs triangle-free reduction
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献4

二级参考文献23

  • 1曲晓英,赵海红.三角连通半无爪图的点泛圈性[J].西南师范大学学报（自然科学版）,2006,31(2):26-29. 被引量：3
  • 2李霄民.判定超欧拉图的一个新方法[J].西南大学学报（自然科学版）,2007,29(4):41-43. 被引量：8
  • 3[1]BONDY J A,MURTY S S. Graph Theory with Applications [M]. New York: American Elsevier,1976.
  • 4[2]CATLIN P A. A Reduction Method to Find Spanning Eulerian Subgraphs [J]. J Graph Theory,1988,12(1):29-44.
  • 5[3]CATLIN P A. Supereulerian Graphs: A Survey [J]. J Graph Theory,1992,16(2): 177-196.
  • 6[4]CATLIN P A. A Reduction Criterion for Supereulerian Graphs [J]. J Graph Theory: 1996,22(2): 151-153.
  • 7[1]Bondy J A,Murty U S R.Graph Theory with Application[M].New York:North-Holland,1976.
  • 8[3]Pulley Blank W R.A Note on Graphs Spanned by Eulerian Graphs[J].J Graph Theory,1979,3(4):309-310.
  • 9[4]Boesch F T,Suffel C,Tindell R.The Spanning Subgraphs of Eulerian Graphs[J].J Graph Theory,1977,1(1):79-84.
  • 10[5]Catlin P A.A Reduction Method to Find Spanning Eulerian Subgraphs[J].J Graph Theory,1988,12(1):29-45.

共引文献14

同被引文献27

  • 1Balbuena C, Garcia-Vazquez P, Marcote X. Reliability of Interconnection Net-works Modelled by a Product of Graphs [J]. Networks, 2006, 48(3) : 114 - 120.
  • 2Bermod J C, Delorme C, Farhi G. Large Graphs with Given Degree and Diamonder I1 [J]. J Combin Theory, Series B, 1984, 36(1): 32--84.
  • 3Bondy J A, Murty U S R. Graph Theory with Applications [M]. New York: American Elsevier, 1976.
  • 4LAI H J. Large Survivable Nets and the Generalized Prisms[J].Discrete Appl Math, 1995, 61(1): 181 --185.
  • 5Smarandaehe F. Only Problems'Not Solutions[M]. Chicago: Xiquan Publishing House, 1993.
  • 6Apostol T M. Introduction to Analytic Number Theory [M]. New York: Spring-Verlag, 1976. 106.
  • 7Zhang Heping. The Connectivity of Z Transformation Graphs of Perfect Matchings of Polyminoes [J]. Discrete Math, 1996, 158: 257- 272.
  • 8Chen Rong-si. Perfect Matchings of Generalized Polyomino Graphs [J]. Graphs and Combinatorics, 2005, 21 : 515 -- 529.
  • 9Zhang Heping, Zhang Fuji. Perfect Matehings of Polyomino Graphs [J]. Graphs and Comhinatorics, 1997, 13:295- 304.
  • 10Zhang Fuji, Zhang Heping. Plane Elementary Bipartite Graphs [J]. Discrete Applied Mathematics, 2000, 105:291 -- 311.

引证文献5

二级引证文献21

西南大学学报（自然科学版）
2008年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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