极大欧拉生成子图为Hamilton圈的图

极大欧拉生成子图为Hamilton圈的图 极大欧拉生成子图为Hamilton圈的图 第24卷第3期 Vo1.24No.3 重庆工商大学(自然科学版) JChongqingTeehnolBusinessUniv.(NatSciEd) 2007年6月 Jun.2007 058X(2007)O3—0218一O3 文章编号:1672— 极大欧拉生成子图为Hamilton圈的图 李霄民 (重庆工商大学理学院,重庆400067) 摘要:对极大欧拉生成子图为Hamilton圈的图作了初步研究,得到了该类图的极大欧拉 生成子图的边数问题,在一定条件下满足3/5一猜想,并给出了一个公开问题;同时也得到了该 类图的最小度及最大度的上界. 关键词:极大欧拉生成子图;Hamilton圈;边数 中图分类号:O157.5文献标识码:A 考虑的图均为无环(1oopless)连通图,除非特别指出,所用的图论术语和记号均沿用文献[1,2]中的 术语和记号. 用O(G) 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示图G中奇度点的集合,即O(G):{EV(G):d()为奇数},用(G)表示图G的分 支数,用(G)表示图G中含有边不交的生成树的个数.若G是一个连通图,且O(G)=,则称G为欧拉 图(Euleriangraph).若G有一个生成子图是欧拉图,则称G是超欧拉图(Supereuleriangraph).用SL表示 全体超欧拉图的集合,即SL={超欧拉图}. 1977年,F.T.Boesch,C.Suffel与R.Tindell在文献[3]中研究了超欧拉图和次欧拉图的问题,并提出 了超欧拉图的边数问题:若G是超欧拉图,那么至少在G中去掉多少边才能得到一个欧拉图.若图G是超 欧拉的,则存在G的极大(边数最多)欧拉生成子图.对于全体超欧拉图,1995年,赖虹建,陈志宏等提出一 个公开问题:. 问题1令卢=ra.inL.Imax{:日是G的欧拉生成子图},问=? 在此之前,美国着名图论专家P.A.Catlin注意到三正则的超欧拉图的欧拉生成子图的边数恰好是整 个图边数的?,故提出如下有名的catlin一猜想(亦称一猜想). caIlin一猜想设G?sL,G?,则G存在一个欧拉生成子图,使得?了2. Ca【lin一猜想 等价于=了2. 1997年,赖虹建,毛经中,李德荣等人发现,如果允许重边存在,则catlin一猜想不成立.长为几的圈再 加上l't一2条重边(1't>4),这时,G的极大(边数最多)的欧拉生成子图H的边数JE(H)I=/7,,而 IE(C)J=2凡一2.从而有=<(凡>4).即caIlin一猜想一般只对简单图而言?同时也 可看出:上述例子中,当凡一?时,有=一号,而?吉是显然的,所以上述公开问题是 针对简单图而言的. 李登信举1ti反例指1ti,即使对于简单图,ca【lin一猜想也不成立.如图1,图G的极大欧拉生成子图 收稿日期:2007—03—06;修回日期:2007一o3—22. 基金项目:重庆市自然科学基金项目(CSTC.2007BA2024)及重庆市教委项目. 作者简介:李霄民(1970一),男,山西稷山县人,硕士,主要从事图论研究. 第3期李霄民:极大欧拉生成子图为Hamilton圈的图2l9 有3m+2条边,从而上述比值<丁2(m>2). 于是有如下猜想: 猜想设c?sL,c?,则c存在一个欧拉生成子图日,使得?. 图1Catlin一猜想的反例G 推广上述方法,得到的一个性质: ,~tl1对于图c(非欧拉图),若存在一个极大欧拉生成子图日,使得=,则一定存在图 c.,使得十詈<,其中日为c.的极大欧拉生成子图. 推论lVc?SL,c是简单图,令p(c)=mgg{:日是c的欧拉生成子图},则p(c)?l』II,Jl 要一般地解决问题1是十分困难的.极大欧拉生成子图为Hamilton圈的图是一类重要的超欧拉图,许 多学者在研究边数问题的过程中发现,该类图边数问题的研究对问题1的研究有重要意义.此处得到一些 初步的结果.并给出了该类图的若干件质. 1极大欧拉生成子图为Hamilton圈的图的边数问题 设c是超欧拉图,日是它的极大(边数最多)欧拉生成子图,则的大小取决于c—()的边数 引理1设G是超欧拉图,日是它的极大(边数最多)欧拉生成子图,则(i)G—E(H)是一森林; (ii)设G—(日)的分支为厂,厂:,…,厂,若Ve=UV?E(H),U?V(Fi),?V(F),则i?_『;(iii)?(G — (日))?2. 证明(i)反设G—E(H)中有圈C,则日UC为一更大欧拉生成子图,与日的极大性矛盾. (ii)若存在e=UV?E(H),存在厂.,满足",?V(Fi),由于G是简单图,则在厂中存在长度大于 1的路P(U,),则(H—e)UP(U,)为一更大欧拉生成子图,与日的极大性矛盾. (iii)证明方法类似于(ii). 定理2设G的极大欧拉生成子图恰为一Hamilton圈日,令IV(G)I=n,若?(G—E(H))>?n,则 G满足?一猜想. 证明由引理1知,G—(日)是一森林,~IE(G—(日))I=n—ccJ(c—(日))<n,= n, 3 IE(G—E(H))+nI5' 2极大欧拉生成子图为Hamilton圈的图的最大度及最小度性质 定理3设G为超欧拉图,若G的极大欧拉生成子图恰为G的Hamilton圈,则:(i)(G)?3; (ii)?(c)?号一1.其中I(c)I=n. 220重庆工商大学(自然科学版)第24卷 证明(i)若6(G)>3,令c为其Hamilton圈,则6(G—E(C))>1,G—E(c)中有圈,据引理1, C不是G的极大欧拉生成子图,矛盾. (ii)若?(G)?号,令d(u)=?(G),令C为其 Hamilton圈,则必存在口l,口2?V(G),且e:D1口2?E(C),使 得,,口?N(u)(图2).则C—e+{O,V.,O,V}为一比C更大 的欧拉生成子图,矛盾. 3问题 要完全确定是十分困难的,在此提出一个问题作为文 章的结束:能否证明对于极大欧拉生成子图为Hamilton圈的 图,了3一猜想成立? " 图2rg=10的情况 参考文献: [1]BONDYJA,MURTYUSR.GraphTheorywithApplication[MJ,Noah—Holland,NewYork,1976 [2]田丰,马仲藩.图与网络流理论[M].北京:科学出版社,1987 [3]BOESCHFT,SUFFELC,TINDELLR,TheSpanningSubgraphsofEulerianGraphs[J].J.ofGraphTheory,1977,I(I): 79—84 [4]CATLINPA.AreductionmethodtofindspanningEuleriansubgraphs[J].J.GraphTheory,1988,12(I):29—45 [5]CHENZH,LAIHJ.Reductiontechniquesforsupereuleriangraphsandrelatedtopics— anupdatefA],in:KuTung—Hsin (ED),CombinatoricsandGraphTheory95Vol[C].WorldScientific.Singapore,London,1995 [6]LIDX,LIDY,MAOJZ.Maximumnumberofedgesinspanningeuleriansubgraph[J].DiscreteMathematics,2004,274 (I):299—302 [7]李霄民,李登信.探索Euler生成子图边数的一种方法[J],工程数 学,2004,21(6):1018—1020;1036 GraphswhosemaximumspanningEuleriansubgrahsareHamiltoncycles LlXiao—min (SchoolofScience,ChongqingTechnologyandBusinessUniversity,Chongqing400067,China) Abstract:Inthispaper,theauthorstudiesgraphswhosemaximumspanningEuleriansubgrahsareHamil— toncycles,andarrivesatthatthesegraphssatisfythe3/5一 confectureongivenconditions.Also,theproperty 0fitsmaximumandminimumdegreeisgiven. Keywords:maximumspanningEuleriansubgraphs;Hamiltoncycle;edge—number 责任编辑:杨祖彬 校对:李翠薇