|
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
V(n,r)={v:v⊂{1,…,n},|v|=r},E(n,r,s)={{v,u}:v,u∈V(n,r),|v∩u|=s};
i.e., the vertices of the graph are r-subsets of the set Rn={1,…,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→∞ are obtained.
Keywords:
distance graph, Hamiltonian path, simple path, clique, hypergraph.
Received: 31.05.2014 Revised: 10.12.2014
Citation:
V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Mat. Zametki, 97:6 (2015), 904–916; Math. Notes, 97:6 (2015), 919–929
Linking options:
https://www.mathnet.ru/eng/mzm10557https://doi.org/10.4213/mzm10557 https://www.mathnet.ru/eng/mzm/v97/i6/p904
|
Statistics & downloads: |
Abstract page: | 350 | Full-text PDF : | 116 | References: | 73 | First page: | 37 |
|