|
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 \in 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: | 275 | Full-text PDF : | 154 | References: | 17 |
|