Quasi_ps-pancyclicity of regular multipartite tournament

DOI10.1007/S00373-023-02689-XMaRDI QIDQ6133660zbMATH OpenOpenAlexFDO

Authors Jiansheng Cai, Guiying Yan

Publication date 21 August 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-023-02689-x

zbMATH Keywords

arc-pancyclicregular multipartite tournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

A digraph \(D\) is arc pancyclic if every arc of \(D\) lies in an \(t\)-cycle for all \(t\) between 3 and \(|V (D)|\). \textit{B. Alspach}'s theorem [Can. Math. Bull. 10, 283--286 (1967; Zbl 0148.43602)] states that every regular tournament is arc pancyclic. It is known that there exist regular multipartite tournaments that are not arc pancyclic. The main goal of the paper under review is to provide an extension of Alspach's theorem to regular multipartite tournaments, by proving that, if \(T\) is a regular \(c\)-partite tournament with partite sets \(V_1,\,V_2,\,\dots,\,V_c\) with \(c\geq 3\), then \(T\) is quasi\(_{\mathrm{ps}}\)-pancyclic, that is, if \([V_i,\, V_j]\neq\emptyset\), then there is a \((V_j,\, V_i)\)-path in \(T\) that transverses exactly \(k\) partite sets for each \(k \in \{4,\dots,\,c\}\). Moreover, the authors also provide a counterexample to a Guo conjecture thus proving that the result presented here is in a certain sense not improvable.

Recommendations

• scientific article; zbMATH DE number 1500178
• The cycle structure of regular multipartite tournaments
• Cycles through a given arc and certain partite sets in almost regular multipartite tournaments
• Cycles containing a given arc in regular multipartite tournaments
• scientific article; zbMATH DE number 1850933

Cites work

• Classes of directed graphs
• Cycles containing a given arc in regular multipartite tournaments
• Cycles in multipartite tournaments
• Cycles of Each Length in Regular Tournaments
• Multipartite tournaments: a survey
• Quasi-hamiltonian paths in semicomplete multipartite digraphs
• The cycle structure of regular multipartite tournaments

Cited in

(2)

• \(\mathrm{Quasi}_{\mathrm{nl}}\)-arc-pancyclic regular multipartite tournaments
• Locally semicomplete multipartite digraphs: a generalization of both locally semicomplete digraphs and semicomplete multipartite digraphs

This page was built for publication: \(\mathrm{Quasi}_{\mathrm{ps}}\)-pancyclicity of regular multipartite tournament

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133660)