Generalized fibonacci maximum path graphs

Martin Charles Golumbic, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

We investigate the following problem: Given integers m and n, find an acyclic directed graph with m edges and n vertices and two distinguished vertices s and t such that the number of distinct paths from s to t (not necessarily disjoint) is maximized. It is shown that there exists such a graph containing a Hamiltonian path, and its structure is investigated. We give a complete solution to the cases (i) m≤2n-3 and (ii) m = kn- 1 2k(k+1)+r for k =1, 2, ..., n- and r=0,1,2.

Original languageEnglish (US)
Pages (from-to)237-245
Number of pages9
JournalDiscrete Mathematics
Volume28
Issue number3
DOIs
StatePublished - 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Generalized fibonacci maximum path graphs'. Together they form a unique fingerprint.

Cite this