On the surface area of the augmented cubes

详细信息    查看全文

• 作者：Eddie Cheng (1) echeng@oakland.edu
  Ke Qiu (2) kqiu@brocku.ca
  Zhizhang Shen (3) zshen@plymouth.edu
• 关键词：Hypercube – ; Augmented cube – ; Surface area – ; Average distance – ; Vertex forwarding index – ; Generating function
• 刊名：The Journal of Supercomputing
• 出版年：2012
• 出版时间：September 2012
• 年：2012
• 卷：61
• 期：3
• 页码：856-868
• 全文大小：460.2 KB
• 参考文献：1. Akers S, Krishnamurthy K (1989) A group theoretic model for symmetric interconnection networks. IEEE Trans Comput 38(4):555–566
  2. Bae M, Bose B (1997) Resource placement in torus based networks. IEEE Trans Comput 46(10):1083–1092
  3. Beivide R, Herrada E, Balc谩zar JL, Arruabarrena A (1991) Optimal distance networks of low degree for parallel computers. IEEE Trans Comput 40(10):1109–1124
  4. Chen Y, Chen M, Tan J (2009) Maximally local connectivity on augmented cubes. In: Proc of the international conference on algorithms and architectures for parallel processing (ICA3PP 2009), Taiwan. LNCS, vol 5574. Springer, Berlin, pp 121–128
  5. Cheng E, Qiu K, Shen Z (2009) A short note on the surface area of star graphs. Parallel Process Lett 19(1):19–22
  6. Cheng E, Qiu K, Shen Z (2011) On the surface areas and average distances of meshes and tori. Parallel Process Lett 21(1):61–75
  7. Cheng E, Qiu K, Shen Z (2011) On the surface area of the asymmetric twisted cube. In: proceedings of the 5th annual international conference on combinatorial optimization and applications
  8. Choudum A, Sunitha V (2002) Augmented cubes. Networks 40:71–84
  9. Choudum A, Sunitha V (2008) Automorphisms of augmented cubes. Int J Comput Math 85:1621–1627
  10. Chung F, Coffman E, Reiman M, Simon B (1987) The forwarding index of communication networks. IEEE Trans Inf Theory 33:224–232
  11. Fertin G, Raspaud A (2001) k-Neighbourhood broadcasting. In: The 8th international colloquium on structural information and communication complexity (SIROCCO’01), pp 133–146
  12. Flajolet P, Sedgewick R (2009) Analytic combinatorics. Cambridge University Press, Cambridge
  13. Goulden IP, Jackson DM (1983) Combinatorial enumeration. Wiley, New York
  14. Graham R, Knuth D, Patashnik O (1989) Concrete mathematics. Addison-Wesley, New York
  15. Heydemann C, Meyer J, Sotteau D (1989) On forwarding indices of networks. Discrete Appl Math 23:103–123
  16. Hsieh S, Cian Y (2010) Conditional edge-fault Hamiltonicity of augmented cubes. Inf Sci 180(13):2596–2617
  17. Hsu H, Chiang L, Tan J, Hsu L (2004) Ring embedding in faulty augmented cubes. In: Proc of the international symposium on parallel architectures, algorithms and networks (ISPAN’04), Hong Kong. IEEE Press, New York
  18. Imani N, Sarbazi-Azad H, Akl SG (2009) Some topological properties of star graphs: the surface area and volume. Discrete Math 309(3):560–569
  19. Knuth DE (2003) Selected papers on discrete mathematics. CSLI
  20. Ma M, Liu G, Xu J (2007) Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes. Parallel Comput 33:36–42
  21. Portier F, Vaughan T (1990) Whitney numbers of the second kind for the star poset. Eur J Comb 11:277–288
  22. Sampels M (2004) Vertex-symmetric generalized Moore graphs. Discrete Appl Math 138:195–202
  23. Sarbazi-Azad H, Ould-Khaoua M, Mackenzie L, Akl S (2001) On some properties of k-ary n-cubes. In: Proc of the eighth international conference on parallel and distributed systems (ICPADS 2001), Korea. IEEE Press, New York, pp 517–524
  24. Sarbazi-Azad H, Khonsari A, Ould-Khaoua M (2010) On the topological properties of grid-based interconnection networks: surface area and volume of radial spheres. Comput J 54(5):726–737
  25. Shen Z, Qiu K, Cheng E (2009) On the surface area of the (n,k)-star graph. Theor Comput Sci 410(52):5481–5490
  26. Sloane N (2011) The On-Line Encyclopedia of Integer Sequences. Available at http://oeis.org/
  27. Wang L, Subramanian S, Latifi S, Srimani PK (2006) Distance distribution of nodes in star graphs. Appl Math Lett 19:780–784
  28. Wilf H (1994) Generatingfunctionology, 2nd edn. Academic Press, San Diego
  29. Xu M, Xu J (2007) The forwarding indices of augmented cubes. Inf Process Lett 101:185–189
• 作者单位：1. Dept. of Mathematics and Statistics, Oakland University, Rochester, MI 48309-4401, USA2. Department of Computer Science, Brock University, St. Catharines, Ontario L2S 3A1, Canada3. Dept. of Computer Science and Technology, Plymouth State University, Plymouth, NH 03264-1595, USA
• ISSN：1573-0484

文摘

The surface area of a communication network centered at a certain vertex, i.e., the number of vertices at the same distance from this given vertex within such a network, provides an important measurement of the broadcasting and other intercommunication capabilities of this network and can find several other applications in network studies. Following a generating function approach, we derive a closed-form expression of the surface area of the recently much discussed augmented cube network and its average distance.