一类Hamilton图

A Kind of Hamiltonian Graph

若P[u ,v]是 2连通无爪图G的最长路 ,设dp(xβ,xα) =︱P[xβ,xα]︱ -1 (xβ<xα) ,d P(xα,xβ) =|P[xα,xβ]|-1 (xα≤xβ) ,其中xα∈N(u) ,xβ∈N(v) ·dP=min{d(xβ,xα)︱xα∈N(u) ,xβ∈N(v) } ·d P =min{d(xα,xβ)︱xα∈N(u) ,xβ∈N(v) } ·设P[u,v]是具有最小dP 的G的最长路·采用反证法 ,将图G分为若干情况 ,利用P[u ,v]的定义 ,证明了 :若G是 2连通无爪图 ,且G的每个导出子图A ,A1都满足 φ(a1,a2 ) 。

It is supposed that P[u,v] is the longest path of a 2 connected claw free graph G,d P(x β,x α)=︱P[x β,x α]︱-1,(x β<x α),d * P(x α,x β)=︱P[x α,x β]︱-1(x α<x β ). Where x α∈N(u),x β∈N(v) .Let d P =min{ d P(x β,x α)｜x α∈N(u), x β∈N(v)}d * P =min{ d * P(x α,x β)｜x α∈N(u),x β∈N(v)} .Let P[u,v] be the longest path of the graph G and d P be minimum in the longst paths of the graph G .The graph G was sorted into several types and the method of reduction to absurdity was used to prove that if the graph G is a 2 connected claw free graph and if each induced subgraph A,A 1 of the graph G satisfies φ(a 1,a 2) , then the graph G is a Hamiltonian graph.