Hamiltonian Paths in Distance Graphs
V. V. Utkin Lomonosov Moscow State University
Abstract:
The object of study is the graph
$$
G(n,r,s)=(V(n,r),E(n,r,s))
$$
with
\begin{align*}
V(n,r)&=\{v : v \subset \{1,\dots,n\}, \, |v|=r\}, \\ E(n,r,s)&=\{\{v,u\} : v,u \in V(n,r), \, |v \cap u|=s\};
\end{align*}
i.e., the vertices of the graph are
$r$-subsets of the set
$\mathcal{R}_n=\{1,\dots,n\}$, and two vertices are connected by an edge if these vertices intersect in precisely
$s$ elements. Two-sided estimates for the number of Hamiltonian paths in the graph
$G(n,k,1)$ as
$n \to \infty$ are obtained.
Keywords:
distance graph, Hamiltonian path, simple path, clique, hypergraph.
UDC:
519.17 Received: 31.05.2014
Revised: 10.12.2014
DOI:
10.4213/mzm10557
Fulltext:
PDF file (512 kB)
