|
Дискретная математика и математическая кибернетика
Гамильтонова связность графов диагональной решетки
Н. В. Прытковa, А. Л. Пережогинba a Novosibirsk State University, 1, Pirogova str., Novosibirsk, 630090, Russia
b Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Аннотация:
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.
Ключевые слова:
hamiltonian connectivity, grid graph, discrete dynamic system.
Поступила 1 декабря 2019 г., опубликована 27 декабря 2019 г.
Образец цитирования:
Н. В. Прытков, А. Л. Пережогин, “Гамильтонова связность графов диагональной решетки”, Сиб. электрон. матем. изв., 16 (2019), 2080–2089
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1188 https://www.mathnet.ru/rus/semr/v16/p2080
|
|