关于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≤n<2-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当n>3·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〈n）使对每个l∈{3，4，…，n}-{m}，G恰有一个长为l的圈且不含长为m的圈，则称G是几乎唯一泛圈图．用Гκ表示具看n＋κ条边和恰有互1（κ＋1）（κ＋2）个圈的简单H图的集合．用Г^＊κ表示具有n＋κ条边恰有2^κ＋κ个圈的简单外可平面H图的集合．本文确定了^-Гκ和Г^＊κ中所有几乎唯一泛圈图，并证明这些图都是简单MCD图．本文还构造了50个含有同胚于K4的子图的几乎唯一泛圈图，并提出了若干问题和猜想．

(3)-泛圈图的一些必要条件

本文主要介绍了一类(3)-泛圈图,即对每一个t,3≤t≤n,阶为n的图G恰有三个长为t的圈,并给出(3)-泛圈图的一些必要条件.

K(1,4)-自由的模k泛圈图(英文)

设G是2-连通的K1,4自由图.本文证明了当δ(G)≥k+1时,G是模k泛圈图.这一结果肯定了猜想2,继而也肯定了Thomassen猜想在2-连通图中的正确性.

泛圈图的一个充分条件

哈密顿图和泛圈图的充分条件是图论中的重要理论问题之一 ,文中讨论了基于禁用子图的泛圈图的一些充分条件 ,给出了泛圈图的一个新的充分条件 :设 G是 2 -连通 ,{K1 ,3,P5,P+ 5}-free的 n阶图 ,则 G是泛圈图或圈 .

泛圈图的一个充分条件

在文[1]中给出定理,设G是一个n-阶2-连通图且δ(G)≥t,若对于G的任意两个不相邻的点u和v,均有|N(u)∪N(v)|≥n-t成立,则G是一个泛圈图或G Kn2,2n.本文的目的在于将此定理的条件减弱,只对图中距离为2的点进行讨论,得出了泛圈图的一个充分条件.文中主要用数学归纳法对定理进行证明,先在引理中给出了几种特殊情况的证明,接着在定理的证明中讨论了一般情形.

拟无爪泛圈图的一个充分条件

设G是一个图.若对G中任意距离为2的点对x,y,总存在u∈N(x)∩N(y),使得N[u]■N[x]∪N[y],则称G是拟无爪图.本文给出了拟无爪图是泛圈图的一个充分条件:设G是n阶2-连通无{K4,P5,A}的拟无爪图,GCn,则G是泛圈图.

Bondy的泛圈图定理的改进

记G=(V,E)是简单图,1971年Bondy得到O re条件下的泛圈图的著名结果:若2连通n阶图G的不相邻的任两点x、y均有d(x)+d(y)≥n,则G是泛圈图或G=Kn/2,n/2.这里进一步研究条件d(x)+d(y)≥n-1,得到:若2连通n阶图G的不相邻的任两点x、y均有d(x)+d(y)≥n-1,则G是泛圈图或G∈{K(Cn+1)/2∨G(n-1)/2,Kn/2,n/2}.本文作者得知最近国际著名权威专家Ho lton等人也得到完全相同的结果,但本证明更简捷.

泛圈图与NC

泛圈图长期以来都是图论中较受重视的课题 ,本文引进 N C对它进行研究 ,得到了与世界著名的图论专家 Bondy引进 ore条件对它进行研究得到的在文 [1 ]中的结果相同的结果 .

关于唯一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－图．

泛圈图与NC

引用邻域并条件对泛圈图进行研究,得到比文献[1]中进一步深刻的结果.

泛圈图的邻域并

让NC2 =min{ N(x) ∪N(y) x ,y∈V(G) ,d(x ,y) =2 } ,得到的主要结果如下 :对于 2连通n(n≤ 6 )阶图G ,如果NC2≥n-δ,则G是泛圈图或kn/2 ,n/2 .此结果改进了图论专家R .J .

一类r-(d_(0),d_(1),…,d_(t-1))-泛圈图的结果

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

泛圈图的邻域并条件的进展(Ⅰ)

泛圈图长期以来都是图论中较受重视的课题 ,图论专家Bondy在文献 [1]中得到条件d(x) +d(y)≥n的泛圈性结果 ,本文进一步得到条件NC≥n-δ下泛圈性的相同结果 ,本文的结果也把Fandree等的文献[2 ]的结果从哈密尔顿图推进到泛圈性 .

与泛圈图有关的一些结果

设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)的界.

泛圈图边数下界研究

研究证明了任意n(≥3)阶图G,当边数m≥n^(2)-3n+6/2时,G是泛圈图,且n^(2)-3n+6/2是边数下界.

顺序偶泛圈图的最少边数及其性质研究

研究构成顺序偶泛圈图的边数,得到顺序偶泛圈图的最少边数,同时研究了最少边数的顺序偶泛圈图的性质,得到了最少边数的顺序偶泛圈图是二部图的结论。

强半无爪泛圈图的一个充分条件

强半无爪图是一类比无爪图更大的图类。本文给出了强半无爪图是泛圈图的一个充分条件:设G是n阶2-连通无{K 4,P5,A}的强半无爪图,G不同构于C n,则G是泛圈图。

一类亚几乎唯一泛圈图

设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p<n,3≤q<n)使对每个l∈{3,4…,n}-{p,q},恰有一个长为l的圈且不含长为p,q的圈,则称G为亚几乎唯一泛圈图。用Γk表示具有n+k条边恰有12(k+1)(k+2)个圈的阶为n的简单Hamilton图的集合。本文确定了Γk中的所有亚几乎唯一泛圈图。并证明这些图除了一个5圈外都是简单MCD图。

泛圈图的一个充分条件

本文证明了:如果G是n(≥9)阶2连通无爪图,且G的每个导出子图Z_1,满足当u,v∈V(G)d_(z_1)(u,v)=2时有|N(u)UN(v)|≥n-3,则G是泛圈图或圈.其中Z_1≌(K_2UK_1)VK_1.