具有二分划(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为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的算法。     

数理科学与化学——哈密尔顿连通图和邻域并条件(Ⅰ)

记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G),xy(?)E(G)},NC_2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2}。1989年Faudree等证明了:若3连通n阶图G,NC≥(2n+1)/3,则G是哈密尔顿连通图。据此进一步研究NC_2≥(2n+1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC_2≥(2n+1)/3,则G是哈密尔顿连通图或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)|相似文献   

哈密尔顿连通图和邻域并条件（Ⅰ）

记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|：x,y∈V（G）mxt∈E（G）|,NC2=min{|N（x）∪N(y)|：x,y∈V(G),d(x,y)=2},1989年Faudree等证明了：若3连通n阶图G,NC≥(2n 1)／3,则G是哈密尔顿连通图。据此进一步研究NC2≥(2n 1)／3,而且研究到2连通图,得到下面结果：若2连通n阶图G,NC2≥(2n 1)／3,则G是哈密尔顿连通图或G=ψ。     

关于图的圈的一个充分条件

设G为n(≥3)阶2连通图,δ≤δ~*≤Δ,对任意x∈V(G),记D(x)={y|y∈V(G)\{x},d(x,y)≤2},D~*(x)={y|y∈(D(x)∪{x}),d(y)<δ~*},本文证明:如果|D~*(x)|相似文献   

无爪图的周长

设 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是哈密顿图。     

2连通2部图周长的下界

设 G(A_1,A_2;E)是以(A_1,A_2)为2分划的2连通的2部图.D(u)={v|v∈V(G),d(u,v)=2};δ_0=min{max{d(u),d(v)}|u,v∈V(G)且 d(u,v=2};D(δ_0)={u|u∈V(G)且d(u)≥δ_0};δ~*为 G 中某一项点度且δ~*≥δ_0,当δ~*>δ_0时δ~*还满足:(i)δ~* 尽可能的大,(ü)对 Vu∈D(δ_0)及 D~*(u)={v|v∈(D(u)U{u}),d(v)<δ~*}有|D~*(u)|相似文献   

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

2-连通图中点不交路的划分问题

给定一个阶为n的2-连通图G=(V;E)及一个正整数k,考虑在邻域并条件下G被分成k条点不交路的问题,得到下面的结果,对G中任何四个独立点x1,x2,y1,y2∈V,满足|NG(x1)∪NG(x2)| |NG(y1)∪NG(y2)|n-k,则G能被分划分k条点不交的路.     

2-连通图的最长圈

设 G是具有围长 g≥5 的 n 阶 2-连通简单图,P=v_1v_2…v_t 是 G的一条最长道路。若λ=min{d(u)+d(v)|u,v∈V(G),uv∈E(G)},δ~*=min{d(v_1),d(v_t)},则G的最长圈为:其中.δ= min{d(v)|v∈V(G)}。     

图的Laplacian谱半径界的可达性

设G为n阶连通的简单图 ,ρ(G)为图G的邻接谱半径 ,μ(G)表示G的Laplacian谱半径。(d1,d2 ,… ,dn) (其中d1≥d2 ≥…≥dn)为G的顶点度序列 ,令r=max{d(u) +d(v) ｜ (u ,v) ∈E(G) } =d(x) +d(y) ,s=max{d(u) +d(v)｜ (u ,v) ∈E(G) - (x ,y) }。该文证明了μ(G)上下界的可达性 :μ(G) =μ≤ 2 + ρ(LG) ,等式成立当且仅当G是偶图。μ(G)≤ 2 + (r- 2 ) (s- 2 ) ,成立等式当且仅当G为半正则偶图或P4 。μ(G)≥d1+ 1,成立等式当且仅当d1=n- 1。     

2-连通图的周长

设G为n阶2-连通图,c(G)为图G的周长,δ=min{d(v)|v∈V(G)},g为G的围长。本文证明:如果g≥5,那么     

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

设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图 .     

关于两类平面图及相关图的L(2,1)-标号问题

图G的L( 2 ,1) 标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1,则 |f(x) -f(y) | 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) | 1 图G的L( 2 ,1)标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L( 2 ,1)标号中的最小数k Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) Δ2 证明了对平面三角剖分图、立体四面体剖分图、平面近四边形剖分图 ,有上述猜想成立     

2连通无爪图的周长

本文给出p阶2连通无爪图G的周长的下界的新的形式:c(G)≥min{p,2λ-2δ+4},这里λ=min{d(u+d(v)│u,v∈V(G),uv∈E(G)}.     

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

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

特殊二部图的上可嵌入性

探讨二部图的上可嵌入性,证明了如下结果：(1)设G=(X,Y；E),定义G~3=(V(G~3),E(G~3)),其中V(G~3)=V(G),E(G~3)=E(G)∪{e=xy|d_G(x,y)：3,x∈X,y∈Y},则G~3是上可嵌入的；(2)设G=(X,Y；E),|X|=|Y|=n(n≥3),对任一对d_G(x,y)=3的x∈X,y∈Y,均有d(x) d(y)≥n 1,则G是上可嵌入的。     

连通图的临界性

通过连通图的研究给出μ-临界 m-连通 m-正则图的一种构造方法.并给出关于μ-临界图的结论:G是4-连通(p,q)图,P≥8,如果存在线x=uv及SV(G)使G-x-S有两个支A,B,u∈A,v∈B,则当|A|≥3或|B|≥3时,G不是μ-临界图.     

二分图中相互独立的圈

证明了下面的结论：设k≥1是一个整数，G＝（V1,V2；E）是一个二分图，满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1，y∈V2，都有d(x) d(y)≥2k 2，并且δ（G）≥2，则G包含k个相互独立的图。