×

On the surface area of the \((n,k)\)-star graph. (English) Zbl 1192.68492

Summary: We present an explicit formula for the surface area of the \((n,k)\)-star graph, i.e., the number of nodes at a certain distance from the identity node in the graph, by identifying the unique cycle structures associated with the nodes in the graph, deriving a distance expression in terms of such structures between the identity node of the graph and any other node, and enumerating those cycle structures satisfying the distance restriction.
The above surface area derivation process can also be applied to some of the other node symmetric interconnection structures defined on the symmetric group when the aforementioned distance expression is available.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W10 Parallel algorithms in computer science
68W05 Nonnumerical algorithms

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akers, S. B.; Krishnamurthy, A group theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026
[2] Sarbazi-Azad, H., On some combinatorial properties of meshes, (Proc. International Symp. on Parallel Architecture, Algorithms and Networks. Proc. International Symp. on Parallel Architecture, Algorithms and Networks, ISPAN’04 (2004), IEEE Comp. Society), 117-122
[3] Sarbazi-Azad, H.; Ould-Khaoua, M.; Mackenzie, L. M.; Akl, S. G., On the combinatorial properties of \(k\)-ary \(n\)-cubes, J. Interconnect. Netw., 5, 1, 79-91 (2004)
[4] Bóna, M., Combinatorics of Permutations (2004), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL · Zbl 1052.05001
[5] Cheng, E.; Qiu, K.; Shen, Z., A short note on the surface area of star graphs, Parallel Process. Lett., 19, 1, 19-22 (2009)
[6] E. Cheng, K. Qiu, Z. Shen, A generating function approach to the surface area of some interconnection networks, Tech. Rep. 2008-03, Dept. of Mathematics and Statistics, Oakland Univ., Rochester, MI, USA, 2008; E. Cheng, K. Qiu, Z. Shen, A generating function approach to the surface area of some interconnection networks, Tech. Rep. 2008-03, Dept. of Mathematics and Statistics, Oakland Univ., Rochester, MI, USA, 2008
[7] E. Cheng, K. Qiu, Z. Shen, On deriving explicit formulas of the surface areas for the arrangement graphs and some of the related graphs, Manuscript, 2008; E. Cheng, K. Qiu, Z. Shen, On deriving explicit formulas of the surface areas for the arrangement graphs and some of the related graphs, Manuscript, 2008 · Zbl 1214.05014
[8] E. Cheng, K. Qiu, Z. Shen, On the surface area of the alternating group graphs and the split star graphs, Tech. Rep. 2008-09, Dept. of Mathematics and Statistics, Oakland Univ., Rochester, MI, USA, 2008; E. Cheng, K. Qiu, Z. Shen, On the surface area of the alternating group graphs and the split star graphs, Tech. Rep. 2008-09, Dept. of Mathematics and Statistics, Oakland Univ., Rochester, MI, USA, 2008
[9] E. Cheng, K. Qiu, Z. Shen, On the surface area of the alternating group networks, Manuscript, 2008; E. Cheng, K. Qiu, Z. Shen, On the surface area of the alternating group networks, Manuscript, 2008
[10] Chiang, W.; Chen, R., The \((n, k)\)-star graph: A generalized star graph, Inform. Process. Lett., 56, 259-264 (1995) · Zbl 1027.68645
[11] Corbett, P. F., Rotator graphs: An efficient topology for point-to-point multiprocessor networks, IEEE Trans. Parallel Distrib. Syst., 3, 5, 622-626 (1992)
[12] Denés, J., The representation of permutation as the product of a minimal number of transpositions and its connection with the theory of graphs, Magy. Tud. Akad. Mat. Kutint., 4, 63-71 (1959) · Zbl 0092.01104
[13] G. Fertin, A. Raspaud, \(k\); G. Fertin, A. Raspaud, \(k\)
[14] Imani, N.; Sarbazi-Azad, H.; Akl, S. G., Some topological properties of star graphs: The surface area and volume, Discrete Math. (2008)
[15] Imani, N.; Sarbazi-Azad1, H.; Zomaya, A. Y., Some properties of WK-recursive and swapped networks, (Proc. Fifth International Symposium on Parallel and Distributed Processing and Applications. Proc. Fifth International Symposium on Parallel and Distributed Processing and Applications, ISPA’07. Proc. Fifth International Symposium on Parallel and Distributed Processing and Applications. Proc. Fifth International Symposium on Parallel and Distributed Processing and Applications, ISPA’07, LNCS, vol. 4742 (2007)), 856-867
[16] Portier, F.; Vaughan, T., Whitney numbers of the second kind for the star poset, European J. Combin., 11, 277-288 (1990) · Zbl 0706.06006
[17] Qiu, K.; Akl, S. G., On some properties of the star graph, VLSI Design, 2, 4, 389-396 (1995)
[18] Riordan, J., An Introduction to Combinatorial Analysis (1980), Wiley: Wiley New York · Zbl 0436.05001
[19] Rotman, J., The Theory of Groups (1973), Allyn and Bacon, Inc.: Allyn and Bacon, Inc. Boston, MA · Zbl 0262.20001
[20] Sampels, M., Vertex-symmetric generalized Moore graphs, Discrete Appl. Math., 138, 195-202 (2004) · Zbl 1034.05019
[21] Shen, Z.; Qiu, K., On the Whitney numbers of the second kind for the star poset, European J. Combinatorics, 29, 7, 1585-1586 (2008) · Zbl 1152.05305
[22] Z. Shen, K. Qiu, An explicit formula of the surface area for the star graph and a proof of its correctness, in: Congressus Numerantium (Proc. Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, CGTC39, Boca Raton, FL, March 3-7, 2008), 192 (December 2008), pp. 115-127; Z. Shen, K. Qiu, An explicit formula of the surface area for the star graph and a proof of its correctness, in: Congressus Numerantium (Proc. Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, CGTC39, Boca Raton, FL, March 3-7, 2008), 192 (December 2008), pp. 115-127 · Zbl 1186.05103
[23] Shen, Z.; Qiu, K.; Cheng, E., On the surface area of the \((n, k)\)-star graph, (Proc. of the 2nd Annual International Conference on Combinatorial Optimization and Applications. Proc. of the 2nd Annual International Conference on Combinatorial Optimization and Applications, COCOA’08. Proc. of the 2nd Annual International Conference on Combinatorial Optimization and Applications. Proc. of the 2nd Annual International Conference on Combinatorial Optimization and Applications, COCOA’08, LNCS, vol. 5165 (2008), Springer: Springer St. Johns, Newfoundland, Canada), 393-404 · Zbl 1168.05364
[24] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences; software available at http://www.research.att.com/ njas/sequences/; N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences; software available at http://www.research.att.com/ njas/sequences/ · Zbl 1274.11001
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.