无爪图的周长

设Ｇ为ｎ阶２连通无爪图，δ－ｍｉｎ｛ｄ（ｘ）│ｘ∈Ｖ（Ｇ）｝，δ－ｍｉｎ｛ｍａｘ（ｄ（ｘ）．ｄ（ｙ））│ｘ，ｙｋ∈Ｖ（Ｇ）．ｄ（ｘ，ｙ）＝３｝．则（ｉ）ｃ（ｇ）≥ｍｉｎ｛ｎ．２δ＋４）；（ｉｉ）当δ≥１／２（ｎ－δ－２）时Ｇ是哈密顿图。

k正则的2.■_(1.3)图的周长

设G为k正则的2连通的不含K_(1.3)的图,则(ⅰ) c(G)≥min{|V(G)|,4k-2},且是最好可能的;(ⅱ)当|V(G)|≤5k-3时,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)|<d(x)。本文证明:G的周长至少为min{n,2max(δ~o,δ~*)}。

2连通的k正则偶图的周长

本文证明2连通的k正则偶图G的周长至少为min{|V(G)|,4k+2},且是最好可能的。

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

设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)|<d(x)，则G中有长至少为min{n,2δ*}的圈。

图的周长

设Ｇ为ｎ阶２连通图，Ｄ（ｘ）＝｛ｙ｜ｙ∈Ｖ（Ｇ），ｄ（ｘ，ｙ）≤２｝，（ｄ＊１，ｄ＊２，⒅，ｄ＊ｊ，⒅，ｄ＊｜Ｄ（ｘ）｜）为Ｄ（ｘ）中所有顶点的度排成的非减度序列，ｄ＊ｄ（ｘ）为（ｄ＊１，ｄ＊２，⒅，ｄ＊ｊ，⒅，ｄ＊｜Ｄ（ｘ）｜）中当ｊ＝ｄ（ｘ）时的度．δ０＝ｍｉｎ｛ｍａｘ（ｄ（ｘ），ｄ（ｙ）｝｜ｘ，ｙ∈Ｖ（Ｇ），ｄ（ｘ，ｙ）＝２｝，δｉ＝ｍｉｎ｛ｄ＊ｄ（ｘ）｜ｘ∈Ｄ（δｉ－１）｝，Ｄ（δｉ－１）＝｛ｘ｜ｘ∈Ｖ（Ｇ），ｄ（ｘ）≥δｉ－１｝，ｉ＝１，２，⒅，ｋ．本文证明（ｉ）若δ０＞δ１，则ｃ（Ｇ）≥ｍｉｎ｛ｎ，２δ０｝；（ｉ）若δ０＜δ１＜δ２＜⒅＜δｋ－１≤δｋ，ｋ≥１，则ｃ（Ｇ）≥ｍｉｎ｛ｎ，２δｋ｝

偶图的周长

设Ｇ（Ａ，Ａ２；Ｅ）为２连通偶图，（Ａ１，Ａ２）为顶点二分划，Ｄ（ｘ）＝｛ｙ｜ｙ∈Ｖ（Ｇ）＼｛ｘ｝，ｄ（ｘ，ｙ）＝２｝，ｄ＾＊ｄ（ｘ）表示Ｄ（ｘ）∪｛ｘ｝中所有的度排成的非减度序列（ｄ＾＊１，ｄ＾＊２，…，ｄ＾＊ｊ，…，ｄ＾＊｜Ｄ（ｘ）｜＋１）中当下标ｊ＝ｄ（ｘ）时的度而当｜Ｄ（ｘ）｜＋１＜ｄ（ｘ）时ｄ＾＊ｄ（ｘ）＝ｄ＾＊｜Ｄ（ｘ）｜＋１。δ０＝ｍｉｎ｛ｄ（ｘ）｜ｘ∈Ｖ（Ｇ）｝。

二连通图的最长圈

本文证明:设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是以(A_1,A_2)为顶点二分划的2连通偶图,D(x)={y|y∈V(G)\{x},d(x,y=2},D(δ_0)={y|y∈V(G),d(y)≥δ_0},δ_0'δ_1皆为尽可能大的自然数且δ_0≤δ_1并满足:(i)对(?)x∈V(G)及D_0*(x)={y|y∈(D(x)U{x}),d(y)<δ_0)有|D_0*(x)|>d(x);(ii)(?)x∈D(δ_0)及D_1*={y|y∈(D(x)U{x}),d(y)<δ_1}有|D_1*(x)|<d(x),则(i)C(G)≥min{2|A_1|,2|A_2|,2(δ_0+δ_1)-4};(ii)当|A_1|=|A_2|,δ_0+δ_1≥|A_1|+1时,G为H图.

不含K_3的图的周长(Ⅲ)

本文给出不含K_3的且非2部图的2连通图的周长的下界.

关于R.Haggkvist猜想的一点注记

本文证明至多为 4k+4 个顶点的、2连通的k 正则偶图为哈密顿图。

不含K_3的图的周长(Ⅱ)

本文给出不含 K_3的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)|<d(u)。本文证明:(i)c(G)≥min{2|A_1|,2|A_2|,2(δ~*+δ_0)-4};(ü)当|A_1|=|A_2|,δ~*+δ_0≥|A_1|+1时 G 为 H 图.

4连通无爪图的最大圈长的一个下界

设Ｇ为ｎ阶４连通无爪图，σ５＝ｍｉｎｘ∈Ｉ５ｄ（ｘ）Ｉ５为Ｇ点的５点独立集｛｝，则ｃ（Ｇ）≥ｍｉｎ｛ｎ，σ５－７｝．

不含 K_3的图的周长

本文给出不含 K_3的2连通图 G 的周长的下界。

二连通偶图的周长

本文给出了二连通偶图 G 的周长的下界的新的形式及 G 为哈密尔顿的新的充分条件.

二连通的二部图的最长圈

本文研究的图 G 为简单的无向的二部图.所用术语和符号除说明外皆同[1].c(G)表示 G 的最长圈的长.以(A_1,A_2)为二分类的二部图记为 G(A_1,A_2).(?)=min{d(v)|v∈V(G)}.已有结果:定理1.设 G(A_1,A_2)为二连通的二部图,则 c(G)≥2min{|A_1|,|A_2|,2δ—2}.定理2.设 G(A_1,A_2)为二连通的二部图,且(?)_i=min{d(v)|v∈A_i}(i=1,