TY - JOUR

T1 - Deficient generalized Fibonacci maximum path graphs

AU - Perl, Y.

AU - Zaks, S.

N1 - Funding Information:
* This work was done whi!c: both authoss were at the Department of Computes Science, University of Dlinois at Usbaza-Cho;npaign, Urbana, IL 63LSO1,a nd was supported in part by the National Science Foundation under grant NSF MCS 7’7-22810

PY - 1981

Y1 - 1981

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0038842059&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038842059&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(81)90063-7

DO - 10.1016/0012-365X(81)90063-7

M3 - Article

AN - SCOPUS:0038842059

VL - 34

SP - 153

EP - 164

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2

ER -