×

Diameter variability of cycles and tori. (English) Zbl 1149.68020

Summary: The diameter of a graph is an important factor for communication as it determines the maximum communication delay between any pair of processors in a network. N. Graham and F. Harary [“Changing and unchanging the diameter of a hypercube”, Discrete Appl. Math. 37/38, 265–274 (1992; Zbl 0756.94021)] studied how the diameter of hypercubes can be affected by increasing and decreasing edges. They concerned whether the diameter is changed or remains unchanged when the edges are increased or decreased. In this paper, we modify three measures proposed in [loc. cit.] to include the extent of the change of the diameter. Let \(D^{-k}(G)\) is the least number of edges whose addition to \(G\) decreases the diameter by (at least) \(k, D^{+0}(G)\) is the maximum number of edges whose deletion from \(G\) does not change the diameter, and \(D^{+k}(G)\) is the least number of edges whose deletion from \(G\) increases the diameter by (at least) \(k\). In this paper, we find the values of \(D^{-k}(C_m), D^{-1}(T_{m,n}), D^{-2}(T_{m,n}), D^{+1}(T_{m,n})\), and a lower bound for \(D^{+0}(T_{m,n})\) where \(C_m\) be a cycle with \(m\) vertices, \(T_{m,n}\) be a torus of size \(m\) by \(n\).

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks

Citations:

Zbl 0756.94021
Full Text: DOI

References:

[1] Bouabdallah, A.; Delorme, C.; Djelloul, S., Edge deletion preserving the diameter of the hypercube, Discrete Applied Mathematics, 63, 91-95 (1995) · Zbl 0836.05041
[2] Dally, W. J.; Towles, B., Principles and Practices of Interconnection Networks (2004), Morgan Kaufmann
[3] Faudree, R. J., Some strong variations of connectivity, Combinatorics - Paul Erdös is Eighty I, 125-144 (1993) · Zbl 0791.05067
[4] Graham, N.; Harary, F., Changing and unchanging the diameter of a hypercube, Discrete Applied Mathematics, 37/38, 265-274 (1992) · Zbl 0756.94021
[5] Harary, F., Recent results and unsolved problems on hypercube theory, (Alavi, Y.; etal., Graph Theory Combinatorics and Applications, vol. 2 (1988), Springer: Springer Berlin), 621-632 · Zbl 0840.05092
[6] Hsu, D. F., On container width and length in graphs, groups, and networks, IEICE Transactions on Fundamentals, E77-A, 668-680 (1994)
[7] Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA · Zbl 0743.68007
[8] Lin, T. C.; Duh, D. R., Constructing vertex-disjoint paths in \((n, k)\)-star graphs, Information Science, 178, 788-801 (2008) · Zbl 1128.68077
[9] Wu, R. Y.; Chen, G. H.; Kuo, Y. L.; Chang, G. J., Node-disjoint paths in hierarchical hypercube networks, Information Science, 177, 4200-4207 (2007) · Zbl 1126.68016
[10] Xu, J., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic publishers · Zbl 1046.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.