关于无爪图中(u,v)-5路存在性的两个定理

TWO THEOREMS ON THE EXISTENCE OF (u,v) 5 PATHS IN CLAW FREE GRAPHS

证明了下列结果：（１）设Ｇ是３连通无爪图，｜Ｖ（Ｇ）｜≥６，且Ｇ的每个导出子图Ａ都满足φ（ａ１，ａ２），那么对任意ｕ，ｖ∈Ｖ（Ｇ），若２≤ｄ（ｕ，ｖ）≤５，则对满足ｄ（ｕ，ｖ）≤ｋ≤５的整数ｋ，Ｇ中存在（ｕ，ｖ）－ｋ路．（２）设Ｇ是３连通无爪图，｜Ｖ（Ｇ）｜≥６，且Ｇ的每个导出子图Ａ都满足φ（ａ１，ａ２），而Ｐ＝ｖ１ｖ２…ｖ５（ｖ１＝ｕ，ｖ５＝ｖ）是Ｇ的（ｕ，ｖ）－４路，Ｇ［Ｖ（Ｐ）］＝Ｋ｜Ｖ（Ｐ）｜，则Ｇ中存在（ｕ，ｖ）－５路．

This paper shows the following results: (1) Let G be a 3 connected claw free graph, and |V(G)|≥6. Suppose that each induced subgraph A of G satisfies φ(a 1,a 2). Then for each pair of vertices u,v∈V(G) with 2≤d(u,v)≤5, there exists a (u,v) k path in G for each integer k satisfying d(u,v)≤k≤5. (2) Let G be a 3 connected claw free graph, and |V(G)|≥6. Assume that each induced subgraph A of G satisfies φ(a 1,a 2). Suppose that P=v 1v 2…v 5(v 1=u,v 5=v) is a (u,v) 4 path in G, and G=K |V(P)| . Then there exists a (u,v) 5 path in G.