RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2019 Volume 16, Pages 2080–2089 (Mi semr1188)

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.

UDC: 519.177

MSC: 05C38

Received December 1, 2019, published December 27, 2019

DOI: 10.33048/semi.2019.16.147



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024