顶点距离大于2的局部化条件与hamiltonian图

对任意正整数i,若图G的导出子图L的顶点满足x,y∈V(L), dL(x,y)=imax{dG(x),dG(y)}≥|G|/2,则称L具有性质DL(i).设C(G)为图G的闭包,本文证明了下述结果任意一个C(G)=G且边连通度≥3的2-连通图,若存在正整数s使得G中的导出子图L满足(i) L(≌)K1.3有性质DL(2);(ii) 任意正整数i,1≤i≤s,L(≌)Bi有性质DL(i);(iii) L(≌)Z s+2有性质DL(s+2),则G为hamiltonian图.由此得到每个边连通度≥3的2-连通{K1.3;Bi,1≤i≤s}-free图, 若C(G)＝G且max{dG(x),dG(y) 对任意导出子图L(≌)Zs+2 ,dL(x,y)=s+2}≥|G|/2,则G一定是hamiltonian图.从而Fan条件中顶点距离可扩展为s+2.     

哈密尔顿图的局部化临域并条件

采用图的局部化临域并条件 ,本文证明了下述结果 :设G是一个p阶 2 -连通图 ,Li- 相似文献   

具有二分划(A1,A2)的2－连通偶图为(A1,A2)Hamilton连通的一个充分条件

给出具有二分划 (A1,A2 )的n阶 2连通偶图G(A1,A2 )为 (A1,A2 )Hamilton连通的定义 ,其中 |A1|=|A2 |·采用反证法 ,将图G分为若干情形 ,利用图G是 2连通的偶图 ,及 |A1|=|A2 |,证明了 ,若n≤ 2δ +2δ - 2时 ,则G是 (A1,A2 )Hamilton连通图 ,其中δ =min{d(x) |x∈V(G) } ,δ =min{max(d(x) ,d(y) ) |d(x ,y) =2 ,x ,y∈V(G) }·     

二连通图的最长圈

本文证明:设G为n阶2连通图,D(x)={y|y∈V(G),d(x,y)≤2},d_d~*(x)表示D(x)中所有的点的度排成的非减度序列:d_1~*,d_2~*,…,d_j~*,d_(j+1)~*,…,d_(|D(x)|)~*中当下标j=d(x)时的度。δ_0=min{d(x)|x∈V(G)},D(δ_(i-1))={x|x∈V(G),d(x)≥δ(i-1)}(i=1,2,…,k),δ_i=min{d_(d(x))~*|x∈D(δ(i-1))}(i=1,2,…,k)且δ_0<δ_1<δ_2<…<δ_(k-1)≤δ_k,则C(G)≥min{n,2δ_k}。此外也给出δ_k的算法。     

L(G)是Hamiltonian的一个充分条件

设G是n≥3阶几乎无桥的连通图,G■K1,n-1,M=abc1c2c3是五个点的路,Bi={a,b,ci,ci 1},i=1,2,V1=V(G)-V(M).若对G中任何同构于M的导出子图满足下列条件之一:(ⅰ)■x0∈V1,|N〈bi〉(x0)|≥3,i=1,2;(ⅱ)xm∈V1,m=1,…,i 1(xs≠xt;s≠t;s,t=1,…,i 1),∑i 1m=1|N〈Bi〉(xm)|≥2i,i=1,2.则G有一个D-闭迹,从而L(G)是Hamiltonian.     

具有二分划(A_1;A_2)的2-连通偶图为(A_1;A_2)Hamilton连通的一个充分条件

给出具有二分划(A1,A2)的n阶2连通偶图G(A1,A2)为(A1,A2)Hamilton连通的定义,其中|A1|=|A2|·采用反证法,将图G分为若干情形,利用图G是2连通的偶图,及|A1|=|A2|,证明了,若n≤2δ+2δ-2时,则G是(A1,A2)Hamilton连通图,其中δ=min{d(x)|x∈V(G)},δ=min{max(d(x),d(y))|d(x,y)=2,x,y∈V(G)}·     

图的离心率值列的研究（英文）

设G为一个图,对任意x∈V（G）,其离心率e(x)定义为e(x)=max{d(x,u)│任意u∈（V（G）}。将G中各点的离心率的值按照（不重复）从小到大排列而得到的数列称为G的离心率值列。现设{ei}1 ≤i≤s为一个非减的整数数列。本得到了下面三个结果：（i){ei}1 ≤i≤s是图的离心率值列当且仅当{ei}1≤i≤s=[e1,es]且e1≥1,es≤2e1;（ii）定义NG（e)={x│x∈V（G）且e(x)=e},若│NG（e)│=1则e=r(G);(iii)有给定离心率值列[r,r s]的图的最小阶f[r,r s]为f[r,r s]={2r s,若0≤s≤r-2;r s 1,若s=r-1或r;这里,[s,s k]表示[r,r s]数列{r-1 i}1≤i≤s 1。     

无爪图的周长

设 G为 n阶 2连通无爪图,δ=min{d(x)|x∈V(G)},δ~*=min{max(d(x),d(y))|x.y∈V(G).d(x.y)=3},则(i)c(G)≥min{n.2δ~*+4};(ii)当 δ~*≥(1/2)(n-δ-2)时 G是哈密顿图。     

图的L(p,q)-标号问题

令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。     

图的周长

设G为n阶2连通图,D(x)={y|y∈V(G)~\(x),d(x,y)≤2},δ_o=min{max{d(x),d(y)}|x,y∈V(G),d(x,y)=2},D(δ_o)={x|x∈V(G),d(x)≥δ_o},δ~*为G中的顶点度且满足:(Ⅰ)δ~*尽可能的大,(Ⅱ)对经(?)x∈D(δ_o)及D~*(x)={y|y∈(D(x)∪{x}),d(y)<δ~*}有|D~*(x)|相似文献   

图的子图匹配数与图的标准化拉普拉斯谱

设图H是图G的一个子图,一个H匹配是与H同构的点不相交的子图集合,将图G中H的匹配数记为v(H,G)。本文用交错不等式来研究v(H,G)与图G的标准化拉普拉斯谱之间的一些关系。     

极大欧拉生成子图为Hamilton圈的图

对极大欧拉生成子图为Hamilton圈的图作了初步研究,得到了该类图的极大欧拉生成子图的边数问题,在一定条件下满足3/5—猜想,并给出了一个公开问题;同时也得到了该类图的最小度及最大度的上界.     

关于圈对完全图的多色Ramsey数

证明了关于k个偶圈对完全图的多色Ramsey数的上界.     

TT''''-free图的最长圈

本文提出了两类新的禁用子图T和T＇.一个图G称为TT＇-free图,若G中不含同构于T或T＇的导出子图,它是比无爪图更广的一个图类.G的一个圈C称为控制圈（简记为D-圈）,若E（G-C）=φ.本文证明了：顶点数不小于3的连通、局部连通TT＇-free图G最长圈为D-圈,且G是局部泛圈的.     

局部化Fan条件的一个推广

对图Ｇ的任一个导出子图Ｌ,若对↓Ａｘ,ｙ∈Ｖ（Ｌ）,ｄＬ（ｘ,ｙ）＝２＝ｍａｘ｛ｄＧ（ｘ）,ｄＧ（ｙ）│≥│Ｇ│／２,则称Ｌ有局部Ｆａｎ性质,证明了下述结果：设Ｇ是一个２－连通图,若其每个导出子图Ｌ＝Ｋ１．３或Ｚ２在Ｇ中均有局部Ｆａｎ性质,则Ｇ是Ｈａｍｉｌｔｏｎｉａｎ图。     

TT-′free图的最长圈

本文提出了两类新的禁用子图T和T′.一个图G称为TT-′free图,若G中不含同构于T或T′的导出子图,它是比无爪图更广的一个图类.G的一个圈C称为控制圈(简记为D-圈),若E(G-C)=Φ.本文证明了:顶点数不小于3的连通、局部连通TT-′free图G最长圈为D-圈,且G是局部泛圈的.     

关于3-正则4-可序图无限类的构造

Lenhard Ng(1997)给出k-可序(k-ordered)哈密尔顿图的定义,并证明了每一个(k 1)-Hamilton-连通图都是k-可序哈密尔顿图．Faudree J R(2000)将k-可序哈密尔顿图的定义改进为k-可序图．根据Lenhard Ng提出的开问题：是否存在3-正则4-可序哈密尔顿图的无限类,以及Faudree J R给出的可序图的定义．构造了3-正则4-可序图的无限类．     

子图的度与 Dominating 圈

笔者利用子图的度给出了如下结果：对2-连通无爪图 G，若任意同构于 K2的不相邻子图 H1，H2，H3满足：d（H1）＋d（H2）＋d（H3）≥｜G｜-1，则 G 的任意最长圈是 Dominating 圈。     

超欧拉图生成子图边数问题的综述

综述了超欧拉图的生成子图边数问题,包括该问题的提出及研究发展过程,并罗列了两类公开问题:能否证明边数问题的下确界是35,若不能证明,能否找到更小的下确界?对一些著名的超欧拉图类,如具有两棵边不交的生成树的图等,能否证明其满足Catlin-猜想或35-猜想?