Hamiltonian Cycles in Regular 2-Connected Claw-Free Graphs

A known result by Jackson Bill is that every 2-connected k-regular graph on at most 3k vertices is Hamiltonian. In this paper,it is proved that every 2-connected k-regular claw-free graph on at most 5k(k≥10)vertices is Hamiltonian. Moreover, the bound 5k is best possible. A counterexample of a 2-connected k-regular claw-free non-Hamiltonian graph on 5k+1 vertices is given, and it is conjectured that every 3-connected k-regular claw-free graph on at most 12k-7 vertices is Hamiltonian.

LONGEST CYCLES IN 2-CONNECTEDCLAW-FREE GRAPHS

M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.

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

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

HAMILTONIAN CYCLES IN REGULAR GRAPHS

Many results have been obtained in investigating the existence of Hamiltonian cycles in 2-connected, k-regular graphs, see [3], [1], [4], [6] and [2].We consider only simple graphs here and use standard graph theory notations and terminology. We let V(G) and E(G) denote the vertex set and the edge set of graph G respectively.

无爪图的周长

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

偶图的周长

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

关于偶图的周长

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