3-连通无爪图Hamilton连通性一个定理.pdf

3-连通无爪图Hamilton 连通性的一个定理 刘弘，李明楚 大连理工大学软件学院，辽宁大连 (116023) E-mail ：qimokaoshi@163.com 摘 要：hamilton-连通性问题是图论中重要问题之一。O.Ore 已证明了如下的著名定理：对 于n 阶图G 中任意两个不相邻顶点u 和v ，若满足d (u) +d (v) ≥n +1，则G 为 hamilton- 连通的。本文要对无爪图进行讨论，主要证明了：假设G 是n 阶 3-连通无爪图，且设P 是 任意一对顶点 u,v 间在 G 中的最长路。若 G −P 是 hamilton- 连通的， − + N (G −P) {u,x ,x ,v}且N (x ) −{x ,x ,x ,u,v} ≠φ ，则| V(P) |≥min{5δ−8, n} 。 P 2 3 P 3 3 3 2 关键词：3-连通；无爪图；hamilton-连通图 中图分类号：TP393 1. 引 言 本文只讨论有限简单图 G (V(G), E (G)) 。用| G | 表示 V(G) 的基数。如果图G 中不 含有与 K 1,3 同构的导出子图，则称图 G 为无爪图。令 G 为 n 阶图且 r ≤n ，定义 δ (G) =min{ | ∪ N (u) |: S ⊂V(G) 且| S | r }，我们分别定义δ(G ) (或δ ) 为G 中顶点 r u ∈S 最小度、κ(G) 为G 中连通度。如κ ≤α(G[S ]) ，则令δ (S ) 表示S 中任意k 对不相邻顶点 k 在图 G 中度数之和的最小值；κ α(G[S ]) ，令δ (S ) κ(n −1) 。对于图G 的子图H 和 k V(G) 的子集S ，我们分别用G −H 和 G[S ] 表示 V(G) −V(H ) 的导出子图和S 的导出子 图；并用N H (S ) 表示 H 中所有与子集S 中顶点相邻的顶点。令dH (S ) = | N H (S ) | 且 E (H , S ) ={ uv ∈E (G) : u ∈V(H ) 且v ∈S }。如果P x x ...x 是图G 中的一条路，令 G 1 2 t x + = x (1 ≤ i t) 且 x − x ( 1i ≤t ) ， 令 x Px = P[x , x ] = x x ...x ， i i+1 i i−1 i j i j i i+1 j x P −x = P −[x ,x ]= x x ...x ( 1≤i ≤j ≤t ) ，P (x , x ) = P[x , x ] \ {x , x } 。我们仍将 j i j i j j −1 i i j i j i j P (x , x ) 和P[x , x ] 看作相应的顶点集。如果图 G 中存在一条包含G 每个顶点的路，则 i j i j 称之为