کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430546 | 688030 | 2015 | 8 صفحه PDF | دانلود رایگان |
The Knödel graph WΔ,nWΔ,n is a graph of even order n and degree Δ where 2≤Δ≤⌊log2n⌋2≤Δ≤⌊log2n⌋. Most properties of the Knödel graph are known only for WΔ,2ΔWΔ,2Δ and WΔ−1,2Δ−2WΔ−1,2Δ−2. In this paper we study the shortest path problem in WΔ,nWΔ,n for all Δ and n . We give a tight bound on the distance between any two vertices in WΔ,nWΔ,n. We show that for almost all Δ , the presented bound differs from actual distance by at most 2. The proofs are constructive and allow us to present an O(logn)O(logn) time algorithm to construct a short path between any pair of vertices in WΔ,nWΔ,n. The diameter of WΔ,nWΔ,n is known only for n=2Δn=2Δ. Using our results on the shortest path problem, we present tight upper and lower bounds on the diameter of the Knödel graph for all Δ and n.
Journal: Journal of Discrete Algorithms - Volume 31, March 2015, Pages 40–47