Paper Info
Title
Connectivity and diameter in distance graphs
Abstract
For \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $n\in \mathbb{N}$ \end{document}**IMAGE** and \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $D\subseteq \mathbb{N}$ \end{document}**IMAGE** , the distance graph P**IMAGE** has 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**IMAGE** for |D| = 2. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(4), 310-315 2011 © 2011 Wiley Periodicals, Inc.
Year
DOI
Venue
2011
10.1002/net.20397
Networks
Keywords
DocType
Volume
computational problem,connected distance graph,edge set,distance graph,delay issue,circulant graph,wiley periodicals,multiple loop networks,inc. networks,well-studied class,distance graph p,connectivity,diam- eter,. circulant graph,diameter
Journal
57
Issue
ISSN
Citations 
4
0028-3045
6
PageRank 
References 
Authors
0.46
19
3
Name
Order
Citations
PageRank
Lucia Draque Penso119620.46
Dieter Rautenbach2946138.87
Jayme Luiz Szwarcfiter361895.79