Digraphs that have at most one walk of a given length with the same endpoints

作者：Huang, Zejun; Zhan, Xingzhi^*

来源：Discrete Mathematics, 2011, 311(1): 70-79.

DOI：10.1016/j.disc.2010.09.025

• Digraph
• Walk
• Number of arcs
• Tournament

Let Theta(n, k) be the set of digraphs of order n that have at most one walk of length k with the same endpoints. Let theta(n, k) be the maximum number of arcs of a digraph in Theta(n, k). We prove that if n >= 5 and k >= n - 1 then theta(n, k) = n(n - 1)/2 and this maximum number is attained at D if and only if D is a transitive tournament. theta(n, n - 2) and theta(n, n - 3) are also determined.

• 出版日期2011-1-6
• 单位华东师范大学