Deficient generalized Fibonacci maximum path graphs

Y. Perl, S. Zaks

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

The structure of an acyclic directed graph with n vertices and m edges, maximizing the number of distinct paths between two given vertices, is studied. In previous work it was shown that there exists such a graph containing a Hamiltonian path joining the two given vertices, thus uniquely ordering the vertices. It was further shown that such a graph contains k - 1 full levels (an edge (i, j) belongs to level t = j -i) and some edges of level k-a deficient k-generalized Fibonacci graph. We investigate the distribution of the edges in level 3 in a deficient 3-generalized Fibonacci graph, and develop tools that might be useful in extending the results to higher levels.

Original languageEnglish (US)
Pages (from-to)153-164
Number of pages12
JournalDiscrete Mathematics
Volume34
Issue number2
DOIs
StatePublished - 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Deficient generalized Fibonacci maximum path graphs'. Together they form a unique fingerprint.

Cite this