Mathematics (May 2022)

The Extendability of Cayley Graphs Generated by Transposition Trees

  • Yongde Feng,
  • Yanting Xie,
  • Fengxia Liu,
  • Shoujun Xu

DOI
https://doi.org/10.3390/math10091575
Journal volume & issue
Vol. 10, no. 9
p. 1575

Abstract

Read online

A connected graph Γ is k-extendable for a positive integer k if every matching M of size k can be extended to a perfect matching. The extendability number of Γ is the maximum k such that Γ is k-extendable. In this paper, we prove that Cayley graphs generated by transposition trees on {1,2,…,n} are (n−2)-extendable and determine that the extendability number is n−2 for an integer n≥3.

Keywords