کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648910 | 1342435 | 2010 | 4 صفحه PDF | دانلود رایگان |
For n∈Nn∈N and D⊆ND⊆N, the distance graph PnD has vertex set {0,1,…,n−1}{0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}{ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set DD of order at least 22, there is a constant cDcD such that the greatest common divisor of the integers in DD is 11 if and only if for every nn, PnD has a component of order at least n−cDn−cD if and only if for every n≥cD+3n≥cD+3, PnD has a cycle of order at least n−cDn−cD. Furthermore, we discuss some consequences and variants of this result.
Journal: Discrete Mathematics - Volume 310, Issue 23, 6 December 2010, Pages 3417–3420