关于偶图的周长

On the Circumferences of Bipartite Graphs

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

Let G be a 2-connected bipartite graph with bipartition (A1,A2),D (x) = {y|yV(G)\{x}, d(x, y)=2}, D(0) = {y|y V(G), d(y) ≥δ0}. Let 0 and 1, be natural numbers with δ0≤δ1, andδ0,δ1 is also satisfying that: (i) |D0*(x)|<d(x), for any x∈V (G) and D0*(x) = {y|y∈(D(x){x}),d(y)}; (ii) |D,*(x)|<d(x), for any x∈D() and D1*(x) = {y|y∈(D(x) {(x)}, d(y)<};(iii) δ0,δ1 is as large as possible . Then G contains a cycle of length at least min {2|A1|, 2|A2|, 2(δ0+δ1,)-4}, Moreover, if |A1| = |A2|, δ0+δ1≥|A1| + 1, Then G is Hamiltonian Graph.