The number of shortest paths in the (n, k)-star graph

DOI10.1142/S1793830914500517zbMath1303.05087OpenAlexW2104626533MaRDI QIDQ2931914

Zhizhang Shen, Eddie Cheng, Ke Qiu

Publication date: 28 November 2014

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830914500517

zbMATH Keywords

parallel computingminimum factorization of a permutation\((n, k)\)-star graphshortest path enumeration

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Factorials, binomial coefficients, combinatorial functions (05A10) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Parallel numerical computation (65Y05) Distance in graphs (05C12)

Related Items (3)

On the problem of determining which \((n, k)\)-star graphs are Cayley graphs ⋮ Conditional fault-tolerant routing of (n,k)-star graphs ⋮ A complete classification of which \((n,k)\)-star graphs are Cayley graphs

Cites Work

• The number of shortest paths in the arrangement graph
• Diameter, short paths and superconnectivity in digraphs
• On the number of factorizations of a full cycle
• Distance formula and shortest paths for the \((n,k)\)-star graphs
• Minimal factorizations of permutations into star transpositions
• On the surface area of the \((n,k)\)-star graph
• On the number of reduced decompositions of elements of Coxeter groups
• Arrangement graphs: A class of generalized star graphs
• Factoring \(n\)-cycles and counting maps of given genus
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• The \((n,k)\)-star graph: A generalized star graph
• There is no optimal routing policy for the torus.
• Higher dimensional hexagonal networks
• A group-theoretic model for symmetric interconnection networks
• Maximally connected digraphs
• Transposition networks as a class of fault-tolerant robust networks
• Handbook of Graph Theory

This page was built for publication: The number of shortest paths in the (n, k)-star graph