偶圈的Turán数和Wenger图

设G是一个图,G的Tur(a)n数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erd(o)s在1965年给出的偶圈C2m的Tur(a)n数ex(n;C2m)的上界10mn1+1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1+1/m(其中c为一个与n无关的常数),可以知道,当n→+∞时,ex(n;C2m)=O(n1+1/m)(m=2,3,5).n1+1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6), 从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

偶圈的Tur(a)n数和Wenger图

设G是一个图，G的Turan数记作ex（n；G），是指阶数为n的不含G作为子图的图的最大边数．根据Erdos在1965年给出的偶圈C2m的Turan数ex（n；C2m）的上界10mn^1＋1/m和Wenger在1991年构造的偶图Hm（q），并由这种图得到的ex（n；C2m）（m=2，3，5）的下界cn^1＋1/m（其中c为一个与n无关的常数），可以知道，当n→＋∞时，ex（n；C2m）=O（n^1＋1/m）（m=2，3，5）．n^1＋1/m就是ex（n；C2m）的准确阶．给出了Wenger图Hm（q）的一些一般性质，并分别构造了Hm（q）中长为8的圈（m≥4）和Hm（q）中长为12的圈（m≥6），从而证明了不可能由图Hm（q）得到ex（n；C2m）的所有准确阶．     

具有特定分解集的图的Turán数

主要研究了具有特定分解集的图的Turán 数,通过确定图F 的极值图,从而确定ex (n,F) 的精确值.具体来说,确定了通过将P₂∪P₃ 的每条边都用一个3团代替(其中每个团的新顶点都是不同的)而得到的图F₁ 的极值图,证明ex (n,F₁) ;确定了通过将完全二部图K_2,3 中的每条边都用一个5 长圈代替(其中每个圈的新顶点都是不同的)而得到的图F₂的极值图,证明ex (n,F₂)     

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

应用图包装的理论和方法研究n(n≥5)阶(p,q)图的泛圈性,得到当q≥C2p-1-2时是泛圈图的充要条件是:(1)G不为C2,8,C3,8,C4,9,K2∨(K1 K2,2),K1 K2,4;(2)G不为C1,n,C3,7,C2,7,C2,6,C2,5,2K3,K2 K3,K1 K2,3和C4 K1及其支撑子图.     

几类图的最优填充数

运用图的最优填充分解定理和局部最优填充定理,将一些特殊图类G1×G2,S(G),R(G)和双圈图分解为一些可求得最小填充数的图,得到如下结果:(1)F(Pm×Pn)≤(m-2)(n-2),其中m≥2,n≥2;(2)若G是有m条边的n阶2-连通图,则F(S(G))=m F(G);(3)设图G为双圈图,两个诱导圈的圈长分别为p和q,t为这两个圈公共部分的路上的顶点个数(不包括两个端点),则F(G)=p q-t-6.     

一类亚几乎唯一泛圈图

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

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

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

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

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

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

应用图包装的理论和方法研究n(n≥5)阶(p,q)图的泛圈性,得到当q≥C2p-1-2时是泛圈图的充要条件是:(1)G不为C2,8,C3,8,C4,9,K2 ∨((-K1) (-K2.2)),(-K1 K2.4);(2)G不为C1,n,C3,7,C2,7,C2,6,C2,5,(-2K3),(-K2 K3),(-K1 K2,3)和(-C4 K1)及其支撑子图.     

一类新的泛偶圈图

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

D—Cyclic图

在图G中,如果存在圈C使得V(G)╲V(C)是G的独立点集。则说G是一个D-Cyclic图,而C是G的一个D-圈。在本文中,我们证明了下述的Veldman猜想:设G是n阶的k-连通图(k≥2),且对任何k+1条相互隔开的边e_0,e_1,…,e_k,都有sum from i=0 to k d(e_i)>1/3(k+1)(n-2)则G是D—Cyclic图。     

一类偶图的顶点——[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]泛偶圈的。深化了上述结果。     

围长为r的圈布图最大边数的新下界

降为n的图G的圈长分布为序列{C1,C2…,Cn},其中Ci是G中长为i的圈的数目,若图G的圈长分布满足C1＝C2＝…＝Cr-2＝0,Cr＝1,且对i＝r 1,…,n,有Ci≤1,则称图G是围长为r的圈分布图,用fr(n)表示阶为n的围长为r的圈分布图最大可能的边数,本文证明：对每个整数n≥R0（其中：r＝3时,R0=17,r≥4时,R＝3r-[r/2] 5,有fr(n)≥n-r ek t 4 η。     

与泛圈图有关的一些结果

设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-偶泛圈图

设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－图．     

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

阶为n的图G的圈长分布是序列(c1,c2,…cn),其中ci是G中长为i的圈的数目,图G的图长分布满足c1=c2=…=0-1=0且对i=r,r+1,…,n有     

关于CmUnK_2的对角Ramsey数

本文所讨论的图都是有限、无向简单图,记为G=(V,E),其中V、E分別表示图G的顶点集、边集。K_n表示n个顶点的完全图,K_(n,n)表示每部有n个顶点的完全两部图;Pn表示n个顶点的路;Cm表示m个顶点的圈,当m为奇(偶)数时,称Cm为奇(偶圈;CmUnK_2表示顶点数为m 2n的图,其中m个点组成圈Cm,余下2n个点组成nK_2(n个K_2的并图)。     

G7×Sn的交叉数

计算并证明了五阶图G7与星Sn的笛卡尔积交叉数cr(G7×Sn)=Z(5,n)+｜n/2｜,这一结果填补了Mrián Kle(s)(c)关于五阶图与星的笛卡尔积交叉数的一处空白.     

围长不小于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的最大整数 .     

关于边数q ≥ Cp-12-2的(p,q)图的泛圈性研究

应用图包装的理论和方法研究n（n≥5）阶（p,q）图的泛圈性,得到当q≥C2p-1-2时是泛圈图的充要条件是：（1）G不为C2,8,C3,8,C4,9,K2∨（K1＋K2,2）,K1＋K2,4;（2）G不为C1,n,C3,7,C2,7,C2,6,C2,5,2K3,K2＋K3,K1＋K2,3和C4＋K1及其支撑子图.