Advanced search
1 file | 201.72 KB Add to list

On the size of maximally non-hamiltonian digraphs

Author
Organization
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.
Keywords
Maximally non-hamiltonian digraphs, INFINITE FAMILY, CIRCUITS, GRAPHS

Downloads

  • CTZamfirescu-31.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 201.72 KB

Citation

Please use this url to cite or link to this publication:

MLA
Lichiardopol, Nicolas, and Carol Zamfirescu. “On the Size of Maximally Non-Hamiltonian Digraphs.” ARS MATHEMATICA CONTEMPORANEA, vol. 16, no. 1, 2019, pp. 59–66.
APA
Lichiardopol, N., & Zamfirescu, C. (2019). On the size of maximally non-hamiltonian digraphs. ARS MATHEMATICA CONTEMPORANEA, 16(1), 59–66.
Chicago author-date
Lichiardopol, Nicolas, and Carol Zamfirescu. 2019. “On the Size of Maximally Non-Hamiltonian Digraphs.” ARS MATHEMATICA CONTEMPORANEA 16 (1): 59–66.
Chicago author-date (all authors)
Lichiardopol, Nicolas, and Carol Zamfirescu. 2019. “On the Size of Maximally Non-Hamiltonian Digraphs.” ARS MATHEMATICA CONTEMPORANEA 16 (1): 59–66.
Vancouver
1.
Lichiardopol N, Zamfirescu C. On the size of maximally non-hamiltonian digraphs. ARS MATHEMATICA CONTEMPORANEA. 2019;16(1):59–66.
IEEE
[1]
N. Lichiardopol and C. Zamfirescu, “On the size of maximally non-hamiltonian digraphs,” ARS MATHEMATICA CONTEMPORANEA, vol. 16, no. 1, pp. 59–66, 2019.
@article{8588703,
  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.},
  author       = {Lichiardopol, Nicolas and Zamfirescu, Carol},
  issn         = {1855-3966},
  journal      = {ARS MATHEMATICA CONTEMPORANEA},
  keywords     = {Maximally non-hamiltonian digraphs,INFINITE FAMILY,CIRCUITS,GRAPHS},
  language     = {eng},
  number       = {1},
  pages        = {59--66},
  title        = {On the size of maximally non-hamiltonian digraphs},
  url          = {http://dx.doi.org/10.26493/1855-3974.1291.ee9},
  volume       = {16},
  year         = {2019},
}

Altmetric
View in Altmetric
Web of Science
Times cited: