AUTHOREA
Log in
Sign Up
Browse Preprints
LOG IN
SIGN UP
Essential Site Maintenance
: Authorea-powered sites will be updated circa 15:00-17:00 Eastern on Tuesday 5 November.
There should be no interruption to normal services, but please contact us at
[email protected]
in case you face any issues.
Yong-De Feng
Public Documents
1
Hypercube embeddings and Cayley graphs generated by transpositions
Yan-Ting Xie
and 2 more
May 15, 2021
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.