RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2019, том 16, страницы 2080–2089 (Mi semr1188)

Дискретная математика и математическая кибернетика

Гамильтонова связность графов диагональной решетки

Н. В. Прытков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.

УДК: 519.177

MSC: 05C38

Поступила 1 декабря 2019 г., опубликована 27 декабря 2019 г.

DOI: 10.33048/semi.2019.16.147



Реферативные базы данных:


© МИАН, 2024