Mathematics and Computational Sciences

On the degree of the Birkhoff polytope graph

Document Type : Original Article

Authors

Bahman Khosravi 1
Behnam Khosravi 2

1 Department of Mathematics, Qom University of Technology, Qom, Iran.

2 Department of Mathematics, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran.

https://doi.org/10.30511/mcs.2026.2071585.1473
Abstract
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-1)! +(n-2)!+(n-3)! +\cdots 1 \big{)}\rfloor$, where $e$ is the Neper number.

Keywords

Birkhoff Polytope graph
Degree of the graph
Cayley graph

Subjects

[1] Balinski, M. L. & Russakoff, A., (1974) On the assignment polytope, SIAM Rev. 16, 516-525. 
[2] Birkhoff, G., (1946) Tres observaciones sobre el algebra lineal, Univ. Nac. Tucumán Rev. Ser. A, 147-151. 
[3] Huang, Z. Li, C., Swartz, E., & Sze, N., Cliques and independent sets of the Birkhoff polytope graph, https://doi.org/10.48550/arXiv.2212.12655. 
[4] Kane, D., Lovett, S., & Rao, S., (2019) The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes, SIAM Journal on Computing 48(4), 1425-1435
Mathematics and Computational Sciences
Volume 7, Issue 1
Winter 2026
Pages 177-181

  • Receive Date 16 September 2025
  • Revise Date 27 December 2025
  • Accept Date 02 January 2026

Home

Submit Manuscript

Reviewers

Contact Us