摘要
图G=(V,E)被称为点可迹的,如果对任意一点u,G中存在Hamilton链使u为其一端点;图G被称为{u}-Hamilton链连通的,如果对任意v∈V\u,G中存在Ha-milton链使u,v为其两端点。对于任意V_0V,0≤|V_0|≤h(或V_0V\u.0≤|V_0|≤h),如果G\V_0是点可迹的(或{u}-Hamilton连通的),则称G为h-点可迹的(或h-{u}-Hamilton连通的)。本文证明了:若G是h-点可迹的(或h-{u}-Hamilton连通的),则其幂图G^h是(h+2k-2)-点可迹的(或(h+2k-2)-{u}-Hamilton连通的)(|V|≥h+2k+1)。
A graph G = (V, E) is called vertex-traceable, if for any u∈V, there exists a Hamiltonian path in G such that u is an endpoint of the path; G is called Hamiltonian-connected from u, if for any v∈V\u, there exists a Hamiltonian path in G such that u and v are two endpoints of the path. For any F0 V, 0≤|Vo|≤h (or V0 V\u, 0≤ |V0|≤h), if G\V0 is vertex-traceable (or Hamiltonian-connected from u) , then G is called h-vertex-traceable (or h-Hamiltonian-connected from u). In this paper, we will prove: if G is h-vertex-traccable (or h-Hamiltonian-connected from u), then the kth power of G, Gk, is h-vertex-traceable {or (h + 2k- 2) -Hamiltonian-connected from u, with |V|≥h+2k+1}.
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
1990年第2期188-192,共5页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
