|
Discrete mathematics and mathematical cybernetics
Hamiltonian connectivity of diagonal grid graphs
N. V. Prytkova, A. L. Perezhoginba a Novosibirsk State University, 1, Pirogova str., Novosibirsk, 630090, Russia
b Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Abstract:
A graph G is called Hamiltonian connected graph if for every pair of distinct vertices u,v∈V(G) there exists a hamiltonian (u,v)-path in G. In this paper we prove Hamiltonian connectivity of the family of infinite two-dimensional diagonal grid induced subgraphs with added horizontal and vertical border edges. A generalization for multidimensional case is given. These results are applied to prove the existence of discrete dynamic systems with arbitrary control functions with some given functioning properties.
Keywords:
hamiltonian connectivity, grid graph, discrete dynamic system.
Received December 1, 2019, published December 27, 2019
Citation:
N. V. Prytkov, A. L. Perezhogin, “Hamiltonian connectivity of diagonal grid graphs”, Sib. Èlektron. Mat. Izv., 16 (2019), 2080–2089
Linking options:
https://www.mathnet.ru/eng/semr1188 https://www.mathnet.ru/eng/semr/v16/p2080
|
Statistics & downloads: |
Abstract page: | 338 | Full-text PDF : | 189 | References: | 30 |
|