Some 3-connected 4-edge-critical non-Hamiltonian graphs

摘要

Let gamma(G) be the domination number of graph G, thus a graph G is k-edge-critical if gamma(G) = k, and for every nonadjacent pair of vertices u and v, gamma(G + uv) = k - 1. In Chapter 16 of the book "Domination in Graphs - Advanced Topics", D. Sumner cites a conjecture of E. Wojcicka under the form ''3-connected 4-critical graphs are Hamiltonian and perhaps, in general (i.e., for any k >= 4), (k - l)-connected, k-edge-critical graphs are Hamiltonian." In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3-connected 4-edge-critical non-Hamiltonian graphs. (c) 2005 Wiley Periodicals, Inc.