On the degree of the Birkhoff polytope graph

The Birkhoff polytope graph can be considered as the Cayley graph of the symmetric group S_n with respect to \mathcal{C}_n, the set of cycles in S_n. Since the degree of every Cayley graph is a natural bound on several parameters of the graph, in this note by presenting a formula for |\mathcal{C}_n|, the degree of the Birkhoff polytope graph, we prove that it is bounded from above by\lfloor e\big{(}(n-۱)! +(n-۲)!+(n-۳)! +\cdots ۱ \big{)}\rfloor, where e is the Neper number.

کلیدواژه ها:

Birkhoff Polytope graph ، Degree of the graph ، Cayley graph