The number of shortest paths in the arrangement graph

DOI10.1016/j.ins.2013.03.035zbMath1321.05117OpenAlexW2121310230MaRDI QIDQ497229

Ke Qiu, Jerrold W. Grossman, Eddie Cheng, Zhizhang Shen

Publication date: 23 September 2015

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2013.03.035

zbMATH Keywords

shortest pathinterconnection networkarrangement graphbi-colored treeminimum factorization of a permutation

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Paths and cycles (05C38) Distance in graphs (05C12)

Related Items (7)

The number of shortest paths in the (n, k)-star graph ⋮ The symmetry property of (n,k)‐arrangement graph ⋮ Path and cycle fault tolerance of bubble-sort graph networks ⋮ On the eigenvalues of certain Cayley graphs and arrangement graphs ⋮ Efficient processing of \textit{continuous min-max distance bounded query} with updates in road networks ⋮ Cayley graph on symmetric group generated by elements fixing \(k\) points ⋮ Researches for more reliable arrangement graphs in multiprocessor computer system

Cites Work

• Unnamed Item
• Unnamed Item
• A combinatorial proof of symmetry among minimal star factorizations
• Partial Jucys-Murphy elements and star factorizations
• On the number of factorizations of a full cycle
• Distance formula and shortest paths for the \((n,k)\)-star graphs
• Transitive powers of Young-Jucys-Murphy elements are central.
• Minimal factorizations of permutations into star transpositions
• 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
• There is no optimal routing policy for the torus.
• Higher dimensional hexagonal networks
• The Number of Shortest Paths in the (n, k)-Star Graphs
• On deriving explicit formulas of the surface areas for the arrangement graphs and some of the related graphs
• A group-theoretic model for symmetric interconnection networks
• Transposition networks as a class of fault-tolerant robust networks
• A new class of interconnection networks based on the alternating group

This page was built for publication: The number of shortest paths in the arrangement graph