Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 18 min ago
PreprintCC BY 4.0arXiv

The Path Partition Conjecture and 3-(quasi-)Transitive Digraphs

  • Shamik Ghosh
  • Jing Huang
Open at sourcePDFDOICite

Abstract

A digraph D = (V,E) is 3-transitive (respectively, 3-quasi-transitive) if whenever $(u,v,w,z)$ is a directed path of length 3, (u,z) ∈ E (respectively, (u,z) ∈ E or (z,u) ∈ E). These digraphs extend the concepts of transitive and quasi-transitive digraphs, respectively. For 3-transitive and 3-quasi-transitive digraphs, only the strong case has been characterized. In this paper, we introduce the notion of semi-acyclic digraphs and use it to describe completely the structure of 3-transitive and 3-quasi-transitive digraphs. As an application of this type of structure description, we prove that the path partition conjecture holds for the class of extended semi-acyclic digraphs, which generalizes two previously known results on the conjecture.

Related

  1. s-quasi-transitive weakly distance-regular digraphs
    Shuang Li, Yuefeng Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Hamiltonicity and cycle factors in k-quasi-transitive digraphs of large diameter
    Hao Zhang, Panpan Cheng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Quasi-strongly regular digraphs constructed from transitive groups of degree n≤ 110
    Vedrana Mikulić Crnković, Matea Zubović Žutolija
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. An Exact Dominant Degree Condition for Transitive Tournament Factors in Digraphs
    Yufei Chang, Shuo Wei, Jin Yan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On 2-distance-transitive circulant digraphs
    Wei Jin, Cai Xia Li, Ping Shan Li +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ghosh2026path,
  title = {{The Path Partition Conjecture and 3-(quasi-)Transitive Digraphs}},
  author = {Shamik Ghosh and Jing Huang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.14217},
  eprint = {2610.14217},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.14217},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Path Partition Conjecture and 3-(quasi-)Transitive Digraphs
AU  - Shamik Ghosh
AU  - Jing Huang
PY  - 2026
DA  - 2026/10/09
PB  - arXiv
DO  - 10.48550/arxiv.2610.14217
UR  - https://arxiv.org/abs/2610.14217
AB  - A digraph D = (V,E) is 3-transitive (respectively, 3-quasi-transitive) if whenever $(u,v,w,z)$ is a directed path of length 3, (u,z) ∈ E (respectively, (u,z) ∈ E or (z,u) ∈ E). These digraphs extend the concepts of transitive and quasi-transitive digraphs, respectively. For 3-transitive and 3-quasi-transitive digraphs, only the strong case has been characterized. In this paper, we introduce the notion of semi-acyclic digraphs and use it to describe completely the structure of 3-transitive and 3-quasi-transitive digraphs. As an application of this type of structure description, we prove that the path partition conjecture holds for the class of extended semi-acyclic digraphs, which generalizes two previously known results on the conjecture.
ER  -