一类亚几乎唯一泛圈图

设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p相似文献   

由圈得到的一类优美图

刘瑞元在〔1〕中证明一个 n(n≥6)个顶点的圈增加两条弦所得图优美,本文证明圈增加若干弦所得图优美.定理具有4k+r 个顶点的圈 C(r=0,1,2,3),可增加 t(1≤t≤2k)条弦,使所得图 C′优美.定理的证明分4种情况:r=0,l,2,3.引理1 具有4k 个顶点的圈 C,可加上t(0≤t≤2k)条弦,使所得图 C′优美。引理2 具有4k+1个顶点的圈 C,可增加t(1≤t≤2k)条弦,使所得图 C′优美.引理3 具有4k+2个顶点的圈 C,可增加t(1≤t≤2k)条弦,使所得图 C′优美.引理4 具有4k+3个顶点的圈 C,可增加t(1≤t≤2k+1)条弦,使所得图 C′优美.     

与泛圈图有关的一些结果

设r,t,j是正整数,对于n阶哈密顿图G,若对每一个r+tj+i(r+tj+i≤n),G中长为r+i+j的圈恰好有di个,0≤i≤t-1,其中t是di的周期,j是t重复的次数,则称图G为r-(d0,…, dt-1)-泛圈图.本文讨论了r-(3,3,4,3,4,3,3,3)-泛圈图,r-(3,5,5,3)-奇(偶)泛圈图,以及g(0,0,6,…,6)的界.     

围长不小于r的2圈分布图的最大边数

阶为 n的图 G的圈长分布是序列 ( c1,c2 ,…cn) ,其中 ci 是 G中长为 i的圈的数目 ,图 G的圈长分布满足 c1=c2 =… =cr- 1=0且对 i=r,r 1 ,… ,n有 ci≤ 2 ,∑ni=rci>0 ,则称图 G是围长不小于 r的 2圈分布图 ,用 fr( n,2 )表示阶为 n的围长不小于 r的 2圈分布图的最大可能的边数 .证明了对每个整数 n≥ r 2 ,有fr( n,2 )≥ n 2 k -2 r 2 4n -2 4k2 8k 4r2 -1 2 r 5,其中 k=[( 5 6 0 n 6 0 ( r2 -3 r) 85) / 3 0 ],这里 [x]表示不超过 x的最大整数 .     

关于r-(P_0,…,P_(t-1))—泛圈图

若G中长为r+tj+i的圈恰好有Pi(0≤i≤t-1)个,其中r+tj+t-1≤n,j是P_0,…,P_(t-1)重复的次数,则称G为r-(P_0,…,P_(t-1))-泛圈图.主要采用构造法,给出当t=8时r-(P_0,…,P_7)-泛圈图的一些结果 .即设n≥14,≥6若2-3+-3≤n2-2+-2且n-(r_((n,)-1))=s(mod8),s=0,1,…,7时,那么存在一个n阶r-(4,4,4,4,5,5,5,5)泛圈图,其中r=r_(0, λ)+s=﹛2~(λ-4)+3+s,当n≤3·2~(λ-4)+2时n-2~(λ-3)+1+s当n3·2~(λ-4)+2时同时,利用类似的方法证明了r-(1,1,3,3,4,4,5,5)—泛圈图、r-(4,4,4,4,5,5,5,5)—奇(偶)泛圈图以及r-(1,1,3,3,4,4,5,5)奇(偶)泛圈图.进一步,给出相应圈长分布的最小可能边数.     

外可平面图的几乎唯一泛圈性

设G是阶为n的简单Hamilton图,若存在m(3≤m相似文献   

关于Hamilton图的新的圈结构定理

设G是一个n阶图,若对于每一个k (3≤k≤n),图G都含有k-圈,则称图G为泛圈图.泛圈图是圈理论研究中的重要课题.研究得到了Hamilton圈上两个不相邻的点在圈上的距离是3的泛圈性结果.     

一类r-(d0,d1,…,dt-1)-泛圈图的结果

设r,t,j是正整数,若对每一个r+tj+i(r+tj+i≤n),n阶简单图G中长为r+tj+i的圈恰好有di个,0≤i≤t?1,其中t是di的周期数,j是t重复的次数,则称图G为r-(d0,…,dt?1)-泛圈图.主要讨论了r-(6?2μ1,6?2μ1,8?2μ1,6?2μ1)-泛圈图,r-(6?2μ1,8?2μ1,...     

Wiener指数,Hyper-Wiener指数与泛圈图

设G=(V,E)为n阶简单连通图,若对每一个k(3≤k≤n),都含有长度为k的圈Ck,则称G为泛圈图。本文主要利用图及其补图的Wiener指数、hyper-Wiener指数,给出具有最小度条件的简单连通图是泛圈图的充分条件。     

关于唯一r-偶泛圈图

设r≥4且r是偶整数．阶为2n的偶图G被称为唯一r-偶泛圈图，如果对每个偶整数t，r≤t≤2n，G恰含一个长为t的圈，且G不含长小于，的圈．若G是唯一r-偶泛圈圈，则称G是r-UB-图．证明了恰好存在6个外可平面的r-UB-图和对m≤3恰好存在12个阶为2n和边数为2n＋m的r－UB－图．     

对偶图Kn,n+I的循环(m1,m2,…,mr)-圈分解

mi(1≤i≤r)为偶数且r∑(i=1)mi=2k(k≥1).Kn,n为偶图,I为Kn,n的一因子.证明了Kn,n+I可分解为(m1,m2,…,mr)-圈的充分必要条件为2k│n(n+1)且n为奇数.进一步,Kn,n+I可分解为循环的(m1,m2,…,mr)-圈充分必要条件为2k=n+1且n为奇数.     

一类偶图的顶点——[6,2n]泛偶圈性

一个阶数为2n的偶图G中每个顶点均有长为2k(l≤k≤m)的圈通过,则称G是顶点——[2l,2m]泛偶圈的。作者在文献[3]中证明了如下结果: 设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G中有长为4,6,8,……,2n的圈。除非G是长为6的圈。本文从连通性出发,证明了满足上述条件的图G是顶点——[6,2n]泛偶圈的。深化了上述结果。     

偶图Kn,n\I的(m1,m2,…,mr)-圈分解

mi(1≤i≤r)为偶数且∑ri=1mi=2k,k≥1,Kn,n为偶图,I为Kn,n的一因子.证明了Kn,n\I可分解为(m1,m2,…,mr)-圈的充分必要条件为2k|n(n-1)且n为奇数.进一步,Kn,n\I可分解为循环的(m1,m2,…,mr)-圈的充分必要条件为2k=n-1且n为奇数.     

一类新的泛偶圈图

一个2n阶偶图G,如果有长为2R(2≤R≤n)的圈,则称其为泛偶圈。本文证明了如下结果:设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G是泛偶圈的,除非是长为6的圈。     

Sierpiński-like图的条件着色

分别对Sierpiński-like图的条件着色进行研究,分别给出S~+(n,k)图与S~(++)(n,k)图的条件色数.对于S+(n,k)图,当n≥2时,若1≤r≤k-1,则χ_r(S~+(n,k))=k;若r≥k,n为奇数时,χ_r(S~+(n,k))=k+1,n为偶数时,χ_r(S~+(n,k))=k+3.对于S~(++)(n,k)图,当n≥2时,若1≤r≤k-1,则χ_r(S~(++)(n,k))=k;若r≥k,χ_r(S~(++)(n,k))=k+1.     

3-连通无爪图的度和与泛圈性

若图G中不含同构于k1,3的导出子图,则称G为无爪图.笔者讨论了3-连通爪图中三个顶点的度和与泛圈性之间的关系,给出了图是泛圈的一个充分条件,得到了如下结果:设图G是n阶3-连通无爪图,如果σ3(G)≥n+1,则G是泛圈的.     

边数q≥C_(p-1)~2-1的(p,q)图的泛圈性研究

泛圈图长期以来是图论中研究的重要课题之一,该文利用图的包装理论研究图的泛圈性,得到n阶(p,q)图G当边数q≥C2p-1-1时G为泛圈图的充要条件.     

边数q≥C2p-1-1的(p,q)图的泛圈性研究

泛圈图长期以来是图论中研究的重要课题之一,该文利用图的包装理论研究图的泛圈性,得到n阶(p,q)图G当边数q≥C2p-1-1时G为泛圈图的充要条件.     

由圈长分布确定的偶图

阶为n的图G的圈长分布是序列(c1，c2，…，cn)，其中ci是图G中长为i的圈数，作者得到如下结果：设n≤r≤min{n 6，2n-3}，则Kn,r是由它的圈长分布确定的。     

K1,4-自由图的模5泛圈性

一个长为Z的圈称为s（mod k）-圈是指l≡s mod k,其中k和s均为自然数,图G称为模k泛圈的是指对任意的s（O≤s〈k）,都包含s（mod k）-圈．若图是模k泛圈的．则称图为模k泛圈图．讨论了K1,4-自由,6-正则圈的模5泛圈性．