Hypercube embeddings and Cayley graphs generated by transpositions

A graph is called a partial cube if it can be embedded into a hypercube isometrically. In this paper, we study a class of Cayley graphs-Cayley graphs generated by transpositions-and show that a Cayley graph Gamma generated by transpositions is a partial cube if and only if Gamma is a bubble sort graph. This result enhances a result of Alahmadi et al. in 2016: BSn is a partial cube. As a corollary, we give the analytical expressions of the Wiener indices of bubble sort graphs.

Automated summary

This paper studies a class of Cayley graphs generated by transpositions and proves that this class of graphs is a partial cube if and only if it is a bubble sort graph. Furthermore, analytical expressions for the Wiener indices of bubble sort graphs are provided.