图的周长

设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为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为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)|相似文献   

具有二分划(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=(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=ψ。     

具有二分划(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=(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=φ。     

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是一个整数，G＝（V1,V2；E）是一个二分图，满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1，y∈V2，都有d(x) d(y)≥2k 2，并且δ（G）≥2，则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)}。     

3－W_n图的优美性

证明了在齿轮图ｎ个齿的顶端各加上三条长度为１的边所得的图是优美的，从而对齿轮图的优美性作了推广．     

关于Km，n并图的优美性

对于自然数k，m，n，本文给出一类非连通图↑k∪↓i=1Kmi.ni；通过构造标号函数的方法，证明了当max{mi，ni}≥3，min{mi，ni}≥2(i=1，2，…，k)时这类图既是优美图，也是交错图；从而给出构造一类任意个图的并图是优美图的一种方法，拓宽了优美图及其应用的道路。     

图U∧C_(4,m_i)from i=1 to n的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了一类任意n个二分图∧C4,m的并图4,1inmiC=U∧是优美图,且是交错图.     

再论图Pn^3的优美性

给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的.     

任意n个完备二分图的并图的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图.     

一类串图的优美性

给出了一些图的优美标号,特别给出了串图ωm1,m2,mn,mn＋1当m1,m2,…,mn≡0（mod4）,mn＋1≡3（mod4）的优美标号,以及串图ωm1,m2,,m2n当mi≡2（mod4）（i=1,2,…,2n）,m2k-1＜m2k,（k=1,2,…,n）时的优美标号.     

图∪ from i=1 to n(F_(mi,4))的优美性

给出图∪ni=1Fmi,4 的一类非连通图 ,并证明这类图是优美图 ,且也是交错图 .     

Hamilton图的代数刻划

运用矩阵方法,给出了连通图是Ｈａｍｉｌｔｏｎ图的一个代数刻划     

关于图n∪i=1(～P)4和n∪i=1(～P)8的优美性

棱柱图(～P)n是由2个回路v1,v2,v3,…,vn和u1,u2,u3,…,un,加上边uivi后所组成的图形.图n∪i=1(～P)4是n个(～P)4的不交并图,图n∪i=1(～P)8是n个(～P)8的不交并图,证明了2类非连通图n∪i(～P)4和n∪i=1(～P)8是优美图且是交错图.     

关于图∪（i=1）n4和∪（i=1）n8的优美性

棱柱图n是由2个回路v1,v2,v3,…,v n和u1,u2,u3,…,un,加上边uivi后所组成的图形.图∪ni=14是n个4的不交并图,图∪n i=18是n个8的不交并图,证明了2类非连通图∪n i=14和∪n i=18是优美图且是交错图.