<p>In this paper, we consider a deterministic graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> drawn on the unit square with straight line segments as edges and connect vertices of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Γ</mi> </math></EquationSource> </InlineEquation> using edges of a random geometric graph (RGG) <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$G$</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation> with adjacency distance <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq4.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$r_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>r</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> as relays. We call the resulting graph as a <i>relay</i> RGG and determine sufficient conditions under such relay RGGs exist and are also near optimal, in terms of the graph parameters of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma .$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Γ</mi> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> We then equip edges of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$G$</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation> with independent, exponentially distributed weights and obtain bounds for the maximum possible weight <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">$W_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>W</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> of a relay RGG with a given length <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="13226_2025_780_Article_IEq8.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">$L_n.$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>L</mi> <mi>n</mi> </msub> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

Deviation estimates for extremal relay random geometric graphs

期刊论文
发表日期：

2025年4月1日

查看全文

Ghurumuruhan Ganesan

摘要

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