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 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 every3≤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≥6contains 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.展开更多
基金Supported by the National Natural Sciences Foundation for Young Scientists of China(11701349)the Natural Science Foundation of Shanxi Province,China(202203021211318,202103021224019)。
文摘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 every3≤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≥6contains 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.
