k_(1,s)─free图的局部Hamiltion连通性(英)

设G是K(1,s)－free图,如果对每一个顶点v∈V（G）,有：K（G［N（V）］）≥s—2,（s≥3）,那么每一局部导出子图均包含一个Hamiltion路。     

顶点距离大于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=(V,E)的边集E的一个分划{E~1,…,E~j}叫做G的一个同构分解,如果 (ii) E~j的边导出子图G~j=(V,E~j)彼此同构。G~1,…,G~j叫做G的一组同构因子,如果H≌H~j(≌表示同构),称H可分G,记为H|G。如果G的一组同构因子恰好有t个子图,称G是t可分的,或t可分G,记为t|G。如果|E|=q,t|G的一个明显的必要条件是t整除q、记为t|q。 F.Harary,R.W.Robinson和N.C.Wormald对于完备三分图K(m,n,s),当     

图的(1,f)——奇因子

一个图 G 的(1,f)——奇因子 F 是一个如下定义的支撑子图,即 f 是以▽(G)为定义域,而值域在{1,3,…,2n-1,…}中的函数;对每一个点 v∈V(G),d_F(v)∈{1,3,…,f_(n)}.加纳干雄1987年4月在东京召开的日本全国数学会议上猜想 G 有一个(1,f)一个奇因子当且仅当o(G-S)≤sum from ν∈s to f(v), SV(G).本文给出它的证明.     

K-连通无爪图的最长u-路

本文证明了如下结果:设G是p阶K一连通的无爪图,K>2.G中任意K+1个顶点的独立集{V_1,V_2,…V_(k+1),有又设u∈V(G),为G中最长的u一路,则G[R]中不含(K-2)一路连通子图,从而不含K_(k-1),这里R=V(G)\V(P)。     

哈密尔顿图的一类新的局部化充分条件

设L为图G的一个导出子图 ,若有 x ,y∈V(L) ,只要dL(x ,y) =2就有max{dG(x) ,dG(y) }≥ |G| / 2 ,则称L有局部Fan性质 .该文证明了以下结果 .G是一个 2_连通的 {K1.3 ,B1} -free图 .对任意一个整数s≥ 0 ,若G的任一个导出子图L∈ {Bi,0≤i≤s;Zs+2 }均有局部Fan性质 ,则G是Hamiltonian图 ,除非s=2且G H9.由此得到每个 2_连通的 {K1.3 ,Bi,0≤i≤s;Zs+2 }_free图除s =2且该图同构于H9外 ,均为Hamiltonian图 .     

图的独立数与分数一致性

设G是一个顶点集为V(G),最小度为δ(G),独立数为α(G)的图,k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V(F)都有dh G(x)=k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ(G)≥k+2,且α(G)≤4k(δ-k-1)/(k+1)2,则图G是一个分数k一致图。     

K1,n-自由图中的(g,f)-因子

设图G是连通的K1,n-自由图,即不包含K1,n作为导出子图的图．g(x),f(x)是定义在V(G)上的非负整数函数,且g(x)≤f(x)．若G的一个支撑子图满足对任意的x∈V(F),有g(x)≤dF(x)≤f(x),则称F为G的(g,f)-因子．得到了连通的K1,n-自由图存在(g,f)-因子的与最小度有关的充分条件．     

哈林图中划分成完美对集问题的线性算法

图G=(V,E),正整数K≤|V|,G的顶点是否能划分成k≤K个不相交的集合V1, V2,…,Vk, 使得对于i∈{1,…,k},由Vi诱导的子图是一个完美对集.这个问题是一个NP完全问题.给出在哈林图上求最小K值的算法.算法的时间复杂度是O(n).     

一类剪刀积图HG的亏格

设H和G为连通图,H和G的剪刀积图HG定义为:V(HG)=V(H)×V(G),E(HG)={(u,v)(s,t)|uv∈E(H),st∈E(G)}.利用电压图及其覆盖图的嵌入理论,本文研究了当第一个因子H为一条路,第二个因子G为Cayley图时,这类剪刀积图HG的亏格.本文的结果可视为目前在研究这类图的亏格上的一个补充,且较大程度上推广相关文献的主要结果.     

一类剪刀积图H(○)G的亏格

设H和G为连通图,H和G的剪刀积图H(○)G定义为:V(H(○)G)=V(H)×V(G),E(H(○)G)={(u,v) (s,t)| uv∈E(H),st∈E(G)}.利用电压图及其覆盖图的嵌入理论,本文研究了当第一个因子H为一条路,第二个因子G为Cayley图时,这类剪刀积图H(○)G的亏格.本文的结果可视为目前在研究这类图的亏格上的一个补充,且较大程度上推广相关文献的主要结果.     

稀疏图的(0,1)-松弛强边着色

给定一个图G=(V(G),E(G)),图G的(s,t)-松弛强边着色数是指使得图G有(s,t)-松弛强k边着色的最小k值,记作χ′(s,t)(G).证明了在图G中,如果mad(G)<3,Δ≤7,那么χ′(0,1)(G)≤3Δ-1;同时证明了对于任意一个平面图G,如果g(G)≥7,Δ≥4,那么χ′(0,1)(G)≤[5△/2]     

连通、几乎局部连通爪心独心K1．4-受限图是完全圈可扩的

设G是一个图,B={v∈V(G)|不连通},如果B是独立集,并且v∈B,u∈V(G),使连通,则称G是几乎局部连通图。证明了连通、几乎局部连通K1,4-受限爪心独立图是完全圈可扩的。     

最小度和[a,b」——覆盖图

设 a≤ b是整数,G=(V(G),E(G))是一个图G的一个支撑子图F称为G的一个[a,b]—因子,若对任意的v∈V(G),有a≤d_F,(v)≤b.图G称为是[a,b]—覆盖图,若对G的每一条边,存在G的一个[a,b]）—因子包含它,本文给出了一个图是[a,b]—覆盖图的关于最小度的充分条件,证明了下列结果;设1≤an (a b)-2(bn-1)~(1/2)则G是一个[a,b]—覆盖图.     

完全二部图K_(9,n)的点可区别IE-全染色(英文)

G是一个简单图,G的一个IE全染色f是一个映射,该映射满足:对u,v∈V(G),u≠v,有C(u)≠C(v).图G的一个点可区别IE-全染色f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,且满足:对uv∈E(G),有f(u)≠f(v);对u,v∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv):uv∈E(G)},简称k-VDIET.数min{k:G有一个k-VDIET染色}称为图G的点可区别IE-全色数或简称VDIET色数,记为χievt(G).本文讨论并给出了完全二部图K9,n的点可区别IE-全色数.     

图的最小符号控制函数的充要条件

在图G=（V,E）的顶点集V上定义一个二值函数f=V→{-1,1},使对任何v∈V,f(N[v])≥1,则称f是图G的一个符号控制函数。图的符号控制函数的权重定义为f(V)=∑v∈vf(V),它的最小权重称为图的符号控制数,记为γs(G）达到最小权重的符号控制函数称为图的最小符号控制函数,本文讨论最小符号控制函数的必要条件。     

关于在K1,n-free图中存在正则因子度条件的推广

图被称为K1,n-free图,如果它不含有导出子图K1,n。设G是一个具有顶点集V(G)的图,并设g和f是两个定义在V(G)的函数,使得g(x) f(x)对所有V(G)中的点x都成立。设a=max{g(x)|x∈V(G)},b=min{f(x)|x∈V(G)},并有b,a 2,n b/(a-1) 1(如果存在点v∈V(G)使得f(v)≡1(mod2),假定b n-1)。证明了:每个连通的使得∑x∈V(G)f(x)为偶数的K1,n-free图G有(g,f)-因子,如果它的最小度至少是(n-1)(a 1)b 1「b a(n-1)2(n-1) -n-1b「b a(n-1)2(n-1) 2 n-3.这个结果是K.Ota和T.Tokuda(J.GraphTheory.1996,22:59-64.)关于在K1,n-free图中存在正则因子度条件的推广。     

K_(1,n)—free图的f—因子

图G称为K1,n—free,若图G不包含同构于K1,n的导出子图 .设 f(x)是定义在V(G)上的非负整数函数 ,G的一个支撑子图F称为G的一个f—因子 ,若对任意的ν∈V(G)有dF(ν) =f(ν) .对K1,n—free图存在f—因子涉及到最小度条件进行了研究 ,得到了一个充分条件 .有关定理为本定理的特例 .     

圈的幂图的s-迹连通性

对于图G的任意两个顶点x和y,如果G有一条(x,y)-生成迹,则称图G是迹连通的.给定一个整数s≥0,对于任意点子集X?V(G)并且|X|≤s,如果G-X是迹连通的,则称图G是s-迹连通.设k是一个正整数,图G的k次幂图记为Gk.设t(G)是t一个最大值s使得图G是s-迹连通但不是(s+1)-迹连通,设Cn是一个包含n...     

二分图中存在包含经过给定边的大圈的2-因子的度条件

该文主要证明了若G=(V1,V2;E)是一个满足|V1|=|V2|=n≥sk的二分图,其中k,s,n为3个正整数且k≥2,s≥4,如果σ1,1(G)≥2「(1-1/s)n k﹁,那么对G的任意k条独立边e1,…,ek,G有一个包含k个点不交的圈C1,…,Ck的2-因子,使得ei∈E(Ci),且|Ci|≥2s.