|
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.
Citation:
M. B. Abrosimov, S. A. Suhov, “On the number of optimal $1$-hamiltonian graphs with the number of vertices up to $26$ and $28$”, Prikl. Diskr. Mat. Suppl., 2016, no. 9, 103–105
Linking options:
https://www.mathnet.ru/eng/pdma255 https://www.mathnet.ru/eng/pdma/y2016/i9/p103
|
|