P3-支配图哈密尔顿性的两个充分条件

Two Sufficient Conditions for P_3-dominated Hamiltonian Graphs

在文献[3]中介绍了一个新的图类—P_3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P_3-支配图是哈密尔顿的,但有一个例外图K_(1,1,3),同时,我们也证明了k-连通的(k≥2)的P_3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K_(1,1,3)and K_(2,3).

The class of P3-dominated graphs was introduced recently in [3]. This class properly contains all quasi claw-free graphs, and hence all claw-free graphs. In this paper, weshow that every triangularly connected P3-dominated graph on at least three vertices is hamiltonian, with an exception K1,1,3. Moreover, we prove that a k-connected （k≥ 2） P3-dominated graph is hamiltonian if an（G） ≤ k, with two exceptions K1,1,3 and K2,3.