Abstract
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 Γ generated by transpositions is a partial cube if and only if Γ
is a bubble sort graph. This result enhances a result of Alahmadi et al.
[Math. Meth. Appl. Sci. 39 (2016), 4856–4865]: BSn
is a partial cube. As a corrollary, we give the analytical expressions
of the Wiener indices of bubble sort graphs.