TY - JOUR

T1 - Generalized fibonacci maximum path graphs

AU - Golumbic, Martin Charles

AU - Perl, Yehoshua

N1 - Funding Information:
* The research for this work was carried out while the first author was a visitor at the Weizmann Institute of Science, Rehovot, Israel, and was partially supported by DOE Contract EY-76-C-02-3077. It was concluded at the Courant Institute under NSF Grant MCS-78-03820. ** This work was partially supported by NSF Grant MCS-73-03408 while the second author was a visitor at the University of Illinois.

PY - 1979

Y1 - 1979

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

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

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

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

U2 - 10.1016/0012-365X(79)90131-6

DO - 10.1016/0012-365X(79)90131-6

M3 - Article

AN - SCOPUS:0038842057

VL - 28

SP - 237

EP - 245

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 3

ER -