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

Zejun Huang, Xingzhi Zhan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

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

Original languageEnglish
Pages (from-to)70-79
Number of pages10
JournalDiscrete Mathematics
Volume311
Issue number1
DOIs
StatePublished - 2011

Keywords

  • Digraph
  • Number of arcs
  • Tournament
  • Walk

Cite this