Search Results for ""

Cubic nonhamiltonian graphs are nonhamiltonian graphs that are also cubic. The numbers of connected cubic nonhamiltonian graphs on n=10, 12, ... nodes are 2, 5, 35, 219, ...

A maximally nonhamiltonian graph is a nonhamiltonian graph G for which G+e is Hamiltonian for each edge e in the graph complement of G^_, i.e., every two nonadjacent vertices ...

A nonhamiltonian graph is a graph that is not Hamiltonian. All disconnected graphs are therefore nonhamiltoinian, as are acylic graphs. Classes of connected graphs that are ...

A quartic nonhamiltonian graph is a quartic graph that is nonhamiltonian. A number of such graphs are illustrated above. Van Cleemput and Zamfirescu (2018) gave a 39-vertex ...

A polyhedral nonhamiltonian graph is a graph that is simultaneously polyhedral and nonhamiltonian. The smallest possible number of vertices a nonhamiltonian polyhedral graph ...

A quintic nonhamiltonian graph is a quintic graph that is nonhamiltonian. A number of such graphs are illustrated above. Owens (1980) showed that there exists a ...

A bicubic nonhamiltonian graph is a bicubic (i.e., bipartite cubic graph) that is nonhamiltonian (i.e., that does not possess a Hamiltonian cycle). Tutte (1971) conjectured ...

Lovász (1970) conjectured that every connected vertex-transitive graph is traceable (Gould, p. 33). This conjecture was subsequently verified for several special orders and ...

The Georges graph, illustrated above, is 50-node graph which is the smallest currently known example of a 3-connected bicubic nonhamiltonian graph. It is implemented in the ...

The smallest possible number of vertices a polyhedral nonhamiltonian graph can have is 11, and there exist 74 such graphs. The Goldner-Harary graph (Goldner and Harary 1975a, ...