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. in 2016: BSn is a partial cube. As a corollary, we give the analytical expressions of the Wiener indices of bubble sort graphs.
展开▼
