E-resources
Peer reviewed
-
Feng, Yong-De; Xie, Yan-Ting; Wei, Lina; Xu, Shou-Jun
Discrete Applied Mathematics, 07/2023, Volume: 333Journal Article
Let S be a set of transpositions that generates the symmetric group Sn on n={1,2,…,n}, where n⩾3. The corresponding Cayley graph is denoted by Cay(Sn,S). The transposition generating graph T(S) of S is a graph with vertex set n and with vertices s and t being adjacent in T(S) whenever (st)∈S. A graph Γ is called induced matching extendable (shortly, IM-extendable) if every induced matching of Γ is included in a perfect matching of Γ. In this paper, we proved that Cay(Sn,S) is IM-extendable if and only if T(S) has true twins, where true twins are defined as a pair of vertices such that they have the same closed neighbourhood in T(S). In addition, we give a linear algorithm for checking true twins in T(S).
