Deficient generalized Fibonacci maximum path graphs |
| |
Authors: | Y Perl S Zaks |
| |
Institution: | Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan, Israel;Department of Computer Science, Technion, Haifa, Israel |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|