X. Ma, E. Vumar: Neighborhood Union Conditions for Hamiltonicity of $P_3$-dominated Graphs II, p. 367-373

Abstract:

A graph $G$ is called $P_3$-dominated $(P3D)$ if it satisfies $J (x, y)\cup J' (x, y)\neq \emptyset$ for every pair $(x, y)$ of vertices at distance 2, where $J (x, y) =\{u\vert u\in N(x)\cap N(y)$, $N[u]\subseteq N[x]\cup N[y]\}$ and $J'(x, y) = \{u\vert u\in N(x)\cap N(y)\vert$ if $v\in N(u)\backslash (N[x]\cup N[y])$, then $(N(u)\cup N(x)\cup N(y))\backslash \{x, y, v\}\subseteq N(v)\}$ for $x, y \in V(G)$ at distance $2$}. For a noncomplete graph $G$, the number $NC$ is defined as $NC=\min\{\vert N(x)\cup N(y)\vert$ : $x, y \in V(G)$ and $xy\notin E(G)\}$, for a complete graph $G$, set $NC=\vert V(G)\vert-1$. In this paper, we prove that a 2-connected $P_3$-dominated graph $G$ of order $n$ is hamiltonian if $G\notin \{K_{2,3}, K_{1,1,3}\}$ and $NC(G)\geq (2n-5)/3$, moreover it is best possible.

Key Words: $P_3$-dominated graph, quasi claw-free graph, neighborhood union, hamiltonicity.

2010 Mathematics Subject Classification: Primary 05C45.