Digraphs with maximum number of paths and cycles

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We construct a digraph with the maximum number of simple paths between two specified vertices, for a digraph with a given number of edges. The following cases are considered: digraphs with parallel edges, acyclic simple digraphs and general simple digraphs. The corresponding extremal digraphs are the tri‐chains, the (deficient) Fibonacci digraphs and (if our conjecture is true) the 3‐diamond strings, respectively. The similarity of these three families of digraphs is discussed. The related problem of digraphs with the maximum number of simple cycles for a given number of edges is considered too.

Original languageEnglish (US)
Pages (from-to)295-305
Number of pages11
Issue number3
StatePublished - 1987

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this