Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 23 min ago
PreprintarXiv licencearXiv

Minimal transitive factorizations supported on quasi-threshold graphs

  • Cordelia Yuqiao Li
  • Ricky Ini Liu
Open at sourcePDFDOICite

Abstract

We study the number of minimal transitive factorizations of the identity permutation in Sn into transpositions supported on a quasi-threshold graph. We show that this number is always divisible by $(2n-2)!/n!$, which is the factorization count for a star graph, as shown by Irving and Rattan. To prove this, we give a combinatorial formula for the number of such factorizations as a weighted sum over a subset of the nn−2 factorization trees, which are edge-weighted spanning trees satisfying certain flow constraints.

Related

  1. Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs
    Joel Bassil
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  2. Multi-Way Expansion, Laplacian Gaps, and Imprimitivity in Vertex-Transitive Graphs
    Zejun Huang, Chenxi Yang
    HALPreprintLicence Ouverte 2.0Full textGeneral mathematicsHAL
  3. Vertex-transitive strongly regular graphs in the switching class of doubly transitive two-graphs
    Robert F. Bailey, Gábor P. Nagy, Valentino Smaldore
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Enumeration of small vertex-transitive directed strongly regular graphs
    A. E. Brouwer, Š. Gyürki
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On Edge-Primitive $2$-Arc-Transitive (Bi-)Cayley Graphs
    Hao Nan Chen, Jing Jian Li, Ji Cheng Ma +1
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref

Cite

BibTeXRIS
BibTeX
@misc{li2026minimal,
  title = {{Minimal transitive factorizations supported on quasi-threshold graphs}},
  author = {Cordelia Yuqiao Li and Ricky Ini Liu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.31982},
  eprint = {2609.31982},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.31982},
}
RIS
TY  - UNPB
TI  - Minimal transitive factorizations supported on quasi-threshold graphs
AU  - Cordelia Yuqiao Li
AU  - Ricky Ini Liu
PY  - 2026
DA  - 2026/09/25
PB  - arXiv
DO  - 10.48550/arxiv.2609.31982
UR  - https://arxiv.org/abs/2609.31982
AB  - We study the number of minimal transitive factorizations of the identity permutation in S_n into transpositions supported on a quasi-threshold graph. We show that this number is always divisible by $(2n-2)!/n!$, which is the factorization count for a star graph, as shown by Irving and Rattan. To prove this, we give a combinatorial formula for the number of such factorizations as a weighted sum over a subset of the n^n−2 factorization trees, which are edge-weighted spanning trees satisfying certain flow constraints.
ER  -