The (weak) Bruhat graph of order , also called the bubble-sort graph (Araki and Kikuchi 2007), is the simple graph having all permutations of as vertices, and with a graph edge between pairs of permutations that differ by an adjacent transposition. The -Bruhat graph is the Cayley graph of the symmetric group generated by adjacent transpositions (Hurlbert 2011). The Bruhat graphs of orders 1 to 4 are illustrated above.

Bruhat graphs are antipodal.

The permutations and edges corresponding to are illustrated above.

Special cases are summarized in the following table.

The -Bruhat graph is planar for to 4. For , 6, ..., upper bounds on the ordinary crossing numbers are 120, 4942, ... (E. Weisstein, Nov. 4, 2026), obtained using QuickCross (Clancy et al. 2019), where each search stream is set to continue until one week has elapsed without strictly improving its own best crossing count. Zheng et al. (2016) gave upper bounds of 120 and 5196 for and , respectively, so while the QuickCross results match the former bound, they improve the latter.

See also

Cayley Graph, Transposition, Truncated Octahedral Graph

Explore with Wolfram|Alpha

References

Araki, T. and Kikuchi, Y. "Hamiltonian Laceability of Bubble-Sort Graphs with Edge Faults." Inform. Sci. 177, 2679-2691, 2007. https://doi.org/10.1016/j.ins.2007.01.017.Clancy, K.; Haythorpe, M.; and Newcombe, A. "An Effective Crossing Minimisation Heuristic Based on Star Insertion." J. Graph Algorithms Appl. 23, 135-166, 2019. https://doi.org/10.7155/jgaa.00487.House of Graphs. Bruhat Graphs. Singleton Graph, K2, C6, and Truncated Octahedral Graph.Hurlbert, G. "A Linear Optimization Technique for Graph Pebbling." 28 Jan 2011. https://arxiv.org/abs/1101.5641.Zheng, B.; Yang, Y.; and Xu, X. "An Upper Bound for the Crossing Number of Bubble-Sort Graph ." Util. Math. 101, 309-328, 2016. https://arxiv.org/abs/1211.4433.

Referenced on Wolfram|Alpha

Bruhat Graph

Cite this as:

Weisstein, Eric W. "Bruhat Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BruhatGraph.html

Subject classifications