Premium
Connectivity and diameter in distance graphs
Author(s) -
Penso Lucia Draque,
Rautenbach Dieter,
Szwarcfiter Jayme Luiz
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20397
Subject(s) - circulant matrix , combinatorics , vertex (graph theory) , mathematics , class (philosophy) , graph , enhanced data rates for gsm evolution , discrete mathematics , computer science , artificial intelligence
For \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $n\in \mathbb{N}$ \end{document} and \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $D\subseteq \mathbb{N}$ \end{document} , the distance graph P n Dhas vertex set {0,1,…, n − 1} and edge set { ij | 0 ≤ i,j ≤ n − 1,| j − i | ∈ 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 contributions are hardness results concerning computational problems related to the connectivity and the diameter of distance graphs and a characterization of the connected distance graphs P n Dfor | D | = 2. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(4), 310‐315 2011