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
SN - 0012-365X
VL - 34
SP - 153
EP - 164
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 2
ER -