Connectivity and diameter in distance graphs

Penso, Lucia Draque GND; Rautenbach, Dieter GND; Szwarcfiter, Jayme Luiz

For $n\in \mathbb{N}$ and $D\subseteq \mathbb{N}$, the distance graph $P_n^D$ has vertex set $\{ 0,1,\ldots,n-1\}$ and edge set $\{ ij\mid 0\leq i,j\leq n-1, |j-i|\in D\}$. The class of distance graphs generalizes the important and very well-studied class of circulant graphs which have been proposed for numerous network applications. In view of fault tolerance and delay issues in these applications, the connectivity and diameter of circulant graphs have been studied in great detail. Our main contributions are hardness results concerning computational problems related to the connectivity and diameter of distance graphs and a number-theoretic characterization of the connected distance graphs $P_n^D$ for $|D|=2$.

Cite

Citation style:
Penso Ph.D., L.D., Brown, Rautenbach Prof. Dr. rer. nat. habil., D., Szwarcfiter Prof., J.L., 2009. Connectivity and diameter in distance graphs. Preprint /  Technische Universität Ilmenau, Institut für Mathematik, Preprint /  Technische Universität Ilmenau, Institut für Mathematik 09–12.
Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:
All rights reserved

Export