Generalized fibonacci maximum path graphs

Martin Charles Golumbic; Yehoshua Perl

doi:10.1016/0012-365X(79)90131-6

Generalized fibonacci maximum path graphs

Martin Charles Golumbic
, Yehoshua Perl

Research output: Contribution to journal › Article › peer-review

23 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 language	English (US)
Pages (from-to)	237-245
Number of pages	9
Journal	Discrete Mathematics
Volume	28
Issue number	3
DOIs	https://doi.org/10.1016/0012-365X(79)90131-6
State	Published - 1979
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

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

Cite this

@article{8725ca527943498898fbb6a77b9a8c25,

title = "Generalized fibonacci maximum path graphs",

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.",

author = "Golumbic, \{Martin Charles\} and Yehoshua Perl",

note = "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.",

year = "1979",

doi = "10.1016/0012-365X(79)90131-6",

language = "English (US)",

volume = "28",

pages = "237--245",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

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 - https://www.scopus.com/pages/publications/0038842057

UR - https://www.scopus.com/pages/publications/0038842057#tab=citedBy

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

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

M3 - Article

AN - SCOPUS:0038842057

SN - 0012-365X

VL - 28

SP - 237

EP - 245

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Generalized fibonacci maximum path graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this