共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
讨论欧拉跳跃图,给出一个图是欧拉图,其跳跃图J(G)是欧拉图的充要条件及一个连通图G=(p,q)的跳跃图J(G)是欧拉图的充要条件,即定理1:设G=(p,q)是欧拉图,则J(G)是欧拉图当且仅当q≥5为奇数.定理2:设G=(p,q)是连通图,则J(G)是欧拉图的充要条件是⑴q≥5是奇数且q>ζ 1,每点的度有相同的奇偶性;⑵q≥6是偶数且q>ζ 1,任意一边的两端点的度有相异的奇偶性.其中ζ=max{d|u| d(v)|uv∈E(G)}. 相似文献
3.
王斌 《西南师范大学学报(自然科学版)》2003,28(1):30-32
得到了超欧拉图的一个特征性质:G是简单图,则G是超欧拉图当且仅当G中有边不交路P1,…,Ps,使得E(Pi)连通.利用它可以证明:当m,n不其端点两两不同,并且满足O(G)={Pi的端点|=1,2,…,s},G-∪si=1同时为3时,m×n型矩形网格图是超欧拉图. 相似文献
4.
5.
6.
综述了超欧拉图的生成子图边数问题,包括该问题的提出及研究发展过程,并罗列了两类公开问题:能否证明边数问题的下确界是35,若不能证明,能否找到更小的下确界?对一些著名的超欧拉图类,如具有两棵边不交的生成树的图等,能否证明其满足Catlin-猜想或35-猜想? 相似文献
7.
通过对图的奇顶点的导出子图做研究,得到了由奇顶点的导出子图的性质判定图的超欧拉性的方法,即当图的奇顶点的导出子图满足一定性质时,可得出图的超欧拉性. 相似文献
8.
9.
10.
关于判定超欧拉图的收缩法 总被引:3,自引:0,他引:3
P.A.Catlin提出一个问题:设H是图G的一个连通子图,如果G关于H的收缩图G/H有一个欧拉生成子图,那么在什么条件下G也有一个欧拉生成子图?研究了这一问题,讨论了Catlin提出的用收缩法判定超欧拉图的两个定理,给出了一些实用的超欧拉图的判别方法。 相似文献
11.
李霄民 《重庆工商大学学报(自然科学版)》2007,24(3):218-220
对极大欧拉生成子图为Hamilton圈的图作了初步研究,得到了该类图的极大欧拉生成子图的边数问题,在一定条件下满足3/5—猜想,并给出了一个公开问题;同时也得到了该类图的最小度及最大度的上界. 相似文献
12.
利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 . 相似文献
13.
一个含有生成闭迹的图称为超欧拉图。设G是n阶3-边连通图,若对任意G的边数为3的最小边割E都满足G-E遥每一连通分支的阶至少为(n-1)/10,则或者G是超欧拉图,或者G可收缩为G‘=Petersen图,且G‘的每个顶点在G中的原像是G的一个可折叠子图,其顶点数至少是(n-1)/10。 相似文献
14.
李汝全 《萍乡高等专科学校学报》2003,(4):3-3
关于欧拉函数φ( x)有如下一个性质 :若 m是大于 1的正整数 ,a是整数 ,( a,m) =1 ,ξ通过模 m的简化剩余系 ,则 Σξ{ aξm} =12 φ( m) . (其中 { x} =x -[x], [x]是不超过 x的最大整数 )证明 :因 ( a,m) =1 ,ξ通过模 m的简化剩余系 ,则 aξ也通过模 m的简化剩余系。由带余除法有aξi =mqi +ri 0 相似文献
15.
李登信 《重庆工商大学学报(自然科学版)》2007,24(3):215-217
设G是超欧拉图,X是G的子图.在G中,把X的点收缩为一个点vX,去掉X的边,得到G关于子图X的收缩,记为G/X.引入a—子图的概念,得到了若干a—子图,并表明如何利用a—子图来寻找欧拉生成子图的最大边数. 相似文献
16.
《云南民族大学学报(自然科学版)》2017,(5):376-380
对于一个图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是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件. 相似文献
17.
雷澜 《重庆工商大学学报(自然科学版)》2008,25(3):233-235
研究了无爪图的极大欧拉生成子图边数问题,给出了当其最小度不小于4,且去掉极大欧拉生成子图后图的分支数不小于顶点数的1/4时,catlin-猜想成立;进一步得到了最大度不小于5时,超欧拉无爪图的极大欧拉生成子图一定不是Hamiltion圈的结论. 相似文献
18.
罗小伟 《吉首大学学报(自然科学版)》1994,15(5):22-23
独立集与临界图是图论中的重要概念,它们在数学的其它分支和实际问题中有广泛应用,在文中均有介绍,本文将证明一些临界图的性质。性质1设T1、T2…Tx是G的最大独立集,而X为任何独立集,设…Tk。则证明;首先考虑k=1的情形,显然此处,显然是独立的,因而,至多有a(G)个点,这样,即性质2设G1、G2是连通的a临界图且不同于K2。分裂一点为x1、x2,移动G2的一边(y1,y2),使xi与Yi此一致,这样得出的图是a临界的。证明:设T为G的独立集,如T至多包含X1,X2之一,则和(G2)分别为G1和G2中的独立集,由此,若x1,x2,则T和分别是… 相似文献
19.
不含三角形子图是简化图的一个重要特征.在研究超欧拉图的边数问题中,估计子图的边数是一个有趣的问题.在考察不含三角形子图这一类图时,使用移边法发现了一个估计这类图的边数的一个上界,并且得到了在达到这个上界时,该图所具有的结构. 相似文献
20.
邓依群 《郑州大学学报(理学版)》2003,35(3):20-22
对两个给定的图G和H,以G H表示G和H的联,以G[H]表示G对图H的结合图,证明了如下结果:(1)G H是Menger图当且仅当G和H均为Menger图;(2)若G和H均为Menger图,且G的任一导出子图也是Menger图,则G[H]必为Menger图。 相似文献