On the Circumference of 2-Connected $mathcal{P}_{3}$ -Dominated Graphs

摘要

Let G be a connected graph. For $x, y in V(G)$ at distance 2, we define $J(x, y) = {u|u in N(x) cap N(y), N[u] subseteq N[x] cup N[y]}$ , and $J^{prime}(x, y) = {u|u in N (x) cap N(y)$ , if $v in N(u) setminus (N [x] cup N[y])$ then $(N(u) cup N(x) cup N(y)) setminus {x,y,v} subseteq N(v)}$ . G is quasi-claw-free $({mathcal{QCF}})$ if it satisfies $J(x, y) neq emptyset$ , and G is P 3-dominated( $mathcal{P}_{3}{mathcal{D}}$ ) if it satisfies $J(x,y)cup J^{prime} (x,y) neq emptyset$ , for every pair (x, y) of vertices at distance 2. Certainly ${mathcal{P}}_3 {mathcal{D}}$ contains ${mathcal{QCF}}$ as a subclass. In this paper, we prove that the circumference of a 2-connected P 3-dominated graph G on n vertices is at least min ${3delta+2,n}$ or $G in {mathcal{F}} cup {K_{2,3}, K_{1,1,3}}$ , moreover if $n leq 4delta$ then G is hamiltonian or $G in {mathcal{F}}cup{K_{2,3}, K_{1,1,3}}$ , where ${mathcal{F}}$ is a class of 2-connected nonhamiltonian graphs.