关于Euler生成子图极大边数的一个注记

若图G存在欧拉生成子图,则称G是超欧拉图(supereulerian).常用SL表示全体超欧拉图组成的集合 设G是有n个点的简单图,G∈SL,如果δ(G)≥ 4且δ≥n5-1,则G存在欧拉生成子图H,使得 |E(H) | / |E(G) |≥ 3/5     

超欧拉图判定方法的一个注记

通过对图的奇顶点的导出子图做研究,得到了由奇顶点的导出子图的性质判定图的超欧拉性的方法,即当图的奇顶点的导出子图满足一定性质时,可得出图的超欧拉性.     

关于Catlin的2/3—猜想

G表示一个图 ,若G有一个欧拉生成子图 ,则称G是超欧拉图。Catlin的 2 3—猜想 :设G是超欧拉图 ,G ≠K1,则G存在一个欧拉生成子图H ,使得｜E(H) ｜ ｜E(G) ｜≥ 2 3。笔者证明了对于Cayley图 ,猜想成立。     

极大欧拉生成子图边数的几个定理

利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 .     

超双爪无关图的可折叠性(英文)

称图G是一个超爪,如果它同构于完全二部图K1,2。连接两个超爪的二度顶点而得到的图称为超双爪。一个图称为是超双爪无关图的,如果它没有导出的超双爪。证明了一个连通超双爪无关图的二部图G,当δ(G)≥4时是可折叠的,显然G是超欧拉的。最后,猜测定理1.1和1.2中的条件δ(G)≥4是最优的。     

Euler生成子图边数的一个定理

证明了设G=(V,E)是2-边连通的简单图,| V |=n,δ(G)是G的最小度,若δ(G)≥max{4,n-4/5}时,G存在Euler生成子图H,使得| E(H)|/|E(G)|≥2/3;即此时Catlin的2/3--猜想成立.     

超欧拉图的一个注记

得到了超欧拉图的一个特征性质:G是简单图,则G是超欧拉图当且仅当G中有边不交路P1,…,Ps,使得E(Pi)连通.利用它可以证明:当m,n不其端点两两不同,并且满足O(G)={Pi的端点|=1,2,…,s},G-∪si=1同时为3时,m×n型矩形网格图是超欧拉图.     

一类α-子图

根据相关文献中给出的用以寻找欧拉生成子图极大边数的有效工具α-子图的概念,证明了对于任意G∈SL,Kl,m（l≥3,m≥3）是G的1-1/min{l,m}-子图．     

广义棱柱和补棱柱中的超欧拉图

对于一个图G,它的顶点标号为1,2,…,n,S_n是在{1,2,…,n}上的n次对称群,α∈S_n是一个置换,图G的α-广义棱柱,记作α(G),是指图G的2个复制,G_x和G_y,连同所有置换边(x_i,y_(α(i))(1≤i≤n)所构成的图.图G的补棱柱,记作G G,同构于由G和G的补图G的不交并,再加上一个连接G和G对应顶点的完美匹配构成的图.如果图G有一个生成欧拉子图,那么称G是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件.