ON THE SURFACE AREAS AND AVERAGE DISTANCES OF MESHES AND TORI
Abstract
We present a surface area lemma to characterize the surface area of a product graph in terms of those of its factors via a generating function approach. We then apply this lemma to derive surface area related results for meshes and tori. Moreover, we also provide explicit formulas for the average distances of these networks.
References
D. Banerjee , B. Mukherjee and R. Suryanarayan , The multidimensional torus: Analysis of average hop distance and application as multihop lightwave network, Proc. IEEE International Conference on Communications (ICC'94)3 pp. 1675–1680. Google Scholar- IEEE Transactions on Computers 40(10), 1109 (1991). Crossref, ISI, Google Scholar
-
C. Charalambides , Enumerative Combinatorics ( Chapman & Hall/CRC , Boca Raton, FL , 2002 ) . Google Scholar - Journal of Interconnection Networks 10(3), 189 (2009). Link, Google Scholar
- Journal of Graph Theory 12(2), 229 (1988). Crossref, ISI, Google Scholar
F. Fertin and A. Raspaud , k-Neighbourhood broadcasting, Proc. 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO'01) pp. 133–146. Google Scholar-
P. Flajolet and R. Sedgewick , Analytic Combinatorics ( Cambridge University Press , 2009 ) . Crossref, Google Scholar -
I. P. Goulden and D. M. Jackson , Combinatorial Enumeration ( John Wiley & Sons Inc. , 1983 ) . Google Scholar - Computers & Mathematics with Applications 15(4), 277 (1988). Crossref, ISI, Google Scholar
- Discrete Mathematics 309(3), 560 (2009). Crossref, ISI, Google Scholar
-
W. Imrich , S. Klavžar and D. Rall , Graphs and Their Cartesian Products ( A. K. Peters , Natick, MA , 2008 ) . Crossref, Google Scholar - , Topics in Applied and Theoretical Mathematics and Computer Science, eds.
V. V. Kluev and N. E. Mastorakis (WSEAS Press, 2001) pp. 155–157. Google Scholar - Discrete Applied Mathematics 138, 195 (2004). Crossref, ISI, Google Scholar
H. Sarbazi-Azad , On some combinatorial properties of meshes, Proc. International Symp. on Parallel Architectures, Algorithms and Networks(ISPAN'04) (IEEE Comp. Society, 2004) pp. 117–122. Google Scholar- Theoretical Computer Science 410(52), 5481 (2009). Crossref, ISI, Google Scholar
-
J. Xu , Topological Structures and Analysis of Interconnection Networks ( Kluwer Academic Publishers , Dordrecht, Netherlands , 2001 ) . Crossref, Google Scholar


