The Number of Shortest Paths in the (n, k)-Star Graphs

1. Akers, S.B., Krishnamurthy, B.: A Group Theoretic Model for Symmetric Interconnection Networks. IEEE Trans. on Computers 38(4), 555–566 (1989)

   Article  MathSciNet  MATH  Google Scholar 

2. Cheng, E., Grossman, J., Lipták, L., Qiu, K., Shen, Z.: Distance Formula and Shortest Paths for the (n,k)-Star Graphs. Information Sciences 180, 1671–1680 (2010)

   Article  MathSciNet  MATH  Google Scholar 

3. Chiang, W., Chen, R.: The (n, k)-Star graph: A Generalized Star Graph. Information Processing Letters 56, 259–264 (1995)

   Article  MathSciNet  MATH  Google Scholar 

4. Day, K., Tripathi, A.: Arrangement Graphs: A Class of Generalized Star Graphs. Information Processing Letter 42, 235–241 (1992)

   Article  MathSciNet  MATH  Google Scholar 

5. Denés, J.: The Representation of Permutation as the Product of a Minimal Number of Transpositions and its Connection with the Theory of Graphs. Magyar Tudományos Akadémia. Matematikai Kutatóintézet 4, 63–71 (1959)

   MathSciNet  MATH  Google Scholar 

6. Fàbrega, J., Fiol, M.A.: Maximally Connected Digraphs. J. Graph Theory 13(6), 657–668 (1989)

   Article  MathSciNet  MATH  Google Scholar 

7. García, F., Solano, J., Stojmenović, I., Stojmenović, M.: Higher Dimensional Hexagonal Networks. J. Parallel and Distributed Computing 63, 1164–1172 (2003)

   Article  MATH  Google Scholar 

8. Goupil, A., Schaeffer, G.: Factoring N-Cycles and Counting Maps of Given Genus. Europ. J. Combinatorics 19, 819–834 (1998)

   Article  MathSciNet  MATH  Google Scholar 

9. Gross, J., Yellen, J. (eds.): Handbook of Graph Theory. CRC Press, Boca Raton (2003)

   Google Scholar 

10. Irving, J.: On the Number of Factorizations of a Full Cycle. J. Combinatorial Theory, Series A 113, 1549–1554 (2006)

    Article  MathSciNet  MATH  Google Scholar 

11. Irving, J., Rattan, A.: Factorizations of Permutations into Star Transpositions. Discrete Mathematics 309(6), 1435–1442 (2009)

    Article  MathSciNet  MATH  Google Scholar 

12. Latifi, S., Srimani, P.: Transposition Networks as a Class of Fault-Tolerant Robust Networks. IEEE Trans. on Computers 45(2), 230–238 (1996)

    Article  MathSciNet  MATH  Google Scholar 

13. Marcote, X., Balbuena, C., Pelayo, I.: Diameter, Short Paths and Superconnectivity in Diagraphs. Discrete Mathematics 288, 113–123 (2004)

    Article  MathSciNet  MATH  Google Scholar 

14. Pak, I.: Reduced Decompositions of Permutations in Terms of Star Transpositions, Generalized Catalan Numbers and k-ary Trees. Discrete Mathematics 204, 329–335 (1999)

    Article  MathSciNet  MATH  Google Scholar 

15. Schwiebert, L.: There is no Optimal Routing Policy for the Torus. Information Processing Letters 83, 331–336 (2002)

    Article  MathSciNet  MATH  Google Scholar 

16. Shen, Z., Qiu, K., Cheng, E.: On the Surface Area of the (n,k)-Star Graph. Theoretical Computer Science 410, 5481–5490 (2009)

    Article  MathSciNet  MATH  Google Scholar 

17. Stanley, R.P.: On the Number of Reduced Decompositions of Elements of Coxeter Group. Europ. J. Combinatorics 5, 359–372 (1984)

    Article  MathSciNet  MATH  Google Scholar 

18. Tang, J., Balbuena, C., Lin, Y., Miller, M.: An Open Problem: Superconnectivity of Regular Digraphs with Respect to Semigirth and Diameter. In: Program of International Workshop on Optimal Network Topologies (IWONT 2007), Pilsen-Černice, Czech Republic (September 2007), http://iti.zcu.cz/iwont2007/iwont2007.pdf

Download references