Deviation Estimates for Extremal Relay Random Geometric Graphs

Abstract

In this paper, we consider a deterministic graph~\(Γ\) drawn on the unit square with straight line segments as edges and connect vertices of~\(Γ\) using edges of a random geometric graph (RGG)~\(G\) with adjacency distance~\(r_n\) as relays. We call the resulting graph as a \emph{relay} RGG and determine sufficient conditions under such relay RGGs exist and are also near optimal, in terms of the graph parameters of~\(Γ.\) We then equip edges of~\(G\) with independent, exponentially distributed weights and obtain bounds for the maximum possible weight~\(W_n\) of a relay RGG with a given length~\(L_n.\)

Accepted for publication in Indian Journal of Pure and Applied Mathematics