2015/02/02 by Jun Zhao, Zhao, Jun, Osman Yağan +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mobile Ad Hoc Networks #Opportunistic and Delay-Tolerant Networks #Physics and Society (physics.soc-ph) #Probability (math.PR) #Social and Information Networks (cs.SI) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1502.00404
openalex publication_date 2015/02/02 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
One-dimensional geometric random graphs are constructed by distributing n nodes uniformly and independently on a unit interval and then assigning an undirected edge between any two nodes that have a distance at most rn. These graphs have received much interest and been used in various applications including wireless networks. A threshold of rn for connectivity is known as rn* = (ln n)/(n) in the literature. In this paper, we prove that a threshold of rn for the absence of isolated node is (ln n)/(2 n) (i.e., a half of the threshold rn*). Our result shows there is a curious gap between thresholds of connectivity and the absence of isolated node in one-dimensional geometric random graphs; in particular, when rn equals (cln n)/( n) for a constant c ∈( (1)/(2), 1), a one-dimensional geometric random graph has no isolated node but is not connected. This curious gap in one-dimensional geometric random graphs is in sharp contrast to the prevalent phenomenon in many other random graphs such as two-dimensional geometric random graphs, Erdős-Rényi graphs, and random intersection graphs, all of which in the asymptotic sense become connected as soon as there is no isolated node.