Applied Theory of Automata and Graphs

On the number of optimal $1$-hamiltonian graphs with the number of vertices up to $26$ and $28$

M. B. Abrosimov, S. A. Suhov

Saratov State University, Saratov

Abstract: A graph is called $1$-vertex-hamiltonian ($1$-edge-hamiltonian) one, if it becomes Hamiltonian after deleting any its vertex (edge). $1$-vertex-hamiltonian ($1$-edge-hamilton) graph is optimal if it has the minimum number of edges among all $1$-vertex-hamiltonian ($1$-edge-hamiltonian) graphs with the same number of vertices. In the paper, the previous data on the number of optimal $1$-vertex- and $1$-edge-hamiltonian graphs with the number of vertices up to $26$ are verified, and new data for $28$-vertex graphs are given.

Keywords: optimal $1$-hamiltonian graph, minimal $1$-extension of cycle, fault-tolerance.

UDC: 519.17

DOI: 10.17223/2226308X/9/40