二连通图的最长圈

本文证明:设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的算法。     

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

设G为k正则的2连通的不含K_(1.3)的图,则(ⅰ) c(G)≥min{|V(G)|,4k-2},且是最好可能的;(ⅱ)当|V(G)|≤5k-3时,G是哈密顿的。     

不含 K_3的图的周长

本文给出不含 K_3的2连通图 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)|相似文献   

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

本文证明2连通的k正则偶图G的周长至少为min{|V(G)|,4k+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)|相似文献