loading page

Hypercube embeddings and Cayley graphs generated by transpositions
  • Yan-Ting Xie,
  • Yong-De Feng,
  • Shoujun Xu
Yan-Ting Xie
Lanzhou University

Corresponding Author:[email protected]

Author Profile
Yong-De Feng
Lanzhou University
Author Profile
Shoujun Xu
Lanzhou University
Author Profile


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.
20 Apr 2021Submitted to Mathematical Methods in the Applied Sciences
20 Apr 2021Submission Checks Completed
20 Apr 2021Assigned to Editor
15 May 2021Reviewer(s) Assigned
20 Aug 2021Review(s) Completed, Editorial Evaluation Pending
21 Aug 2021Editorial Decision: Revise Major
23 Aug 20211st Revision Received
23 Aug 2021Submission Checks Completed
23 Aug 2021Assigned to Editor
27 Oct 2021Reviewer(s) Assigned
27 Oct 2021Review(s) Completed, Editorial Evaluation Pending
22 Feb 2022Editorial Decision: Accept
30 Jul 2022Published in Mathematical Methods in the Applied Sciences volume 45 issue 11 on pages 7227-7237. 10.1002/mma.8233