Name
Abstract | ||
|---|---|---|
A graph is called maximally non-hamiltonian if it is non-hamiltonian, yet for any two non-adjacent vertices there exists a hamiltonian path between them. In this paper, we naturally extend the concept to directed graphs and bound their size from below and above. Our results on the lower bound constitute our main contribution, while the upper bound can be obtained using a result of Lewin, but we give here a different proof. We describe digraphs attaining the upper bound, but whether our lower bound can be improved remains open. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.26493/1855-3974.1291.ee9 | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Maximally non-hamiltonian digraphs | Graph,Combinatorics,Hamiltonian (quantum mechanics),Existential quantification,Vertex (geometry),Upper and lower bounds,Hamiltonian path,Directed graph,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 1 | 1855-3966 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Lichiardopol | 1 | 1 | 1.02 |
| Carol T. Zamfirescu | 2 | 38 | 15.25 |