Hamiltonian Properties of the 3-(γ,2)-Critical Graphs

Ewa Wojcicka (Journal of Graph Theory, 14(1990), 205-215) showed that every connected, 3-gamma-critical graph on more than 6 vertices has a Hamiltonian path. Henning et al. (Discrete Mathematics, 161(1996), 175-184) defined a graph G to be k-(gamma,d)-critical graph if gamma(G) = k and gamma(G + uv) = k - 1 for each pair u, v of nonadjacent vertices of G that are at distance at most d apart. They asked if a 3-(gamma,2)-critical graph must contain a dominating path. In this paper, we show that every connected, 3-(gamma, 2)-critical graph must contain a dominating path. Further we show that every connected, 3-(gamma, 2)-critical graph on more than 6 vertices has a Hamiltonian path.