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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics