Scholarlink

<p>A <i>tournament</i> is an orientation of the edges of a complete graph. An arc in a digraph <i>D</i> is <i>pancyclic</i> if it is contained in a cycle of length <i>k</i> for every 3 ≤ <i>k</i> ≤ ∣<i>V</i>(<i>D</i>)∣. An arc <i>uv</i> in a digraph <i>D</i> is <i>k-anticyclic</i> if there is a path from <i>u</i> to <i>v</i> of length <i>k</i> − 1 in <i>D</i>. If for every 3 ≤ <i>k</i> ≤ ∣<i>V</i>(<i>D</i>)∣, an arc <i>uv</i> is <i>k</i>-anticyclic, then we say that <i>uv</i> is <i>anti-pancyclic</i> in <i>D</i>. It has been proved in Discrete Appl. Math. 79 (1997) 127–135 that every arc of a 3-strong and arc-3-cyclic tournament <i>T</i> is <i>k</i>-anticyclic for each <i>k</i> ≥ 4, unless <i>T</i> is isomorphic to two tournaments, each of which has exactly 8 vertices. In J. Combin. Inform. System Sci. 19 (1994) 207–214, Moon showed that every strong tournament contains at least three pancyclic arcs and characterized the tournaments that attain this lower bound. In this paper we investigate the number of antipancyclic arcs in strong tournaments and show that every strong tournament with order <i>n</i> ≥ 6 contains at least four anti-pancyclic arcs unless it is isomorphic to five tournaments, each of which has exactly 6 vertices. Consequently, every strong tournament with order <i>n</i> ≥ 7 contains at least four anti-pancyclic arcs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Anti-pancyclic arcs in strong tournaments

  • 期刊论文

  • 发表日期：

    2026年3月1日

查看全文
  • Wei Meng,
  • Qiao-ping Guo,
  • Yu-bao Guo,
  • Lu Li

摘要

A tournament is an orientation of the edges of a complete graph. An arc in a digraph D is pancyclic if it is contained in a cycle of length k for every 3 ≤ k ≤ ∣V(D)∣. An arc uv in a digraph D is k-anticyclic if there is a path from u to v of length k − 1 in D. If for every 3 ≤ k ≤ ∣V(D)∣, an arc uv is k-anticyclic, then we say that uv is anti-pancyclic in D. It has been proved in Discrete Appl. Math. 79 (1997) 127–135 that every arc of a 3-strong and arc-3-cyclic tournament T is k-anticyclic for each k ≥ 4, unless T is isomorphic to two tournaments, each of which has exactly 8 vertices. In J. Combin. Inform. System Sci. 19 (1994) 207–214, Moon showed that every strong tournament contains at least three pancyclic arcs and characterized the tournaments that attain this lower bound. In this paper we investigate the number of antipancyclic arcs in strong tournaments and show that every strong tournament with order n ≥ 6 contains at least four anti-pancyclic arcs unless it is isomorphic to five tournaments, each of which has exactly 6 vertices. Consequently, every strong tournament with order n ≥ 7 contains at least four anti-pancyclic arcs.