Geodesic
On the size of maximally non-hamiltonian digraphs
Ars Mathematica Contemporanea, Tome 16 (2019) no. 1, pp. 59-66.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.1291.ee9
Keywords: Maximally non-hamiltonian digraphs 
@article{10_26493_1855_3974_1291_ee9,
     author = {Nicolas Lichiardopol and Carol T. Zamfirescu},
     title = {On the size of maximally non-hamiltonian digraphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {59--66},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2019},
     doi = {10.26493/1855-3974.1291.ee9},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1291.ee9/}
}
TY  - JOUR
AU  - Nicolas Lichiardopol
AU  - Carol T. Zamfirescu
TI  - On the size of maximally non-hamiltonian digraphs
JO  - Ars Mathematica Contemporanea
PY  - 2019
SP  - 59
EP  - 66
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1291.ee9/
DO  - 10.26493/1855-3974.1291.ee9
LA  - en
ID  - 10_26493_1855_3974_1291_ee9
ER  - 
%0 Journal Article
%A Nicolas Lichiardopol
%A Carol T. Zamfirescu
%T On the size of maximally non-hamiltonian digraphs
%J Ars Mathematica Contemporanea
%D 2019
%P 59-66
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1291.ee9/
%R 10.26493/1855-3974.1291.ee9
%G en
%F 10_26493_1855_3974_1291_ee9
Nicolas Lichiardopol; Carol T. Zamfirescu. On the size of maximally non-hamiltonian digraphs. Ars Mathematica Contemporanea, Tome 16 (2019) no. 1, pp. 59-66. doi : 10.26493/1855-3974.1291.ee9. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1291.ee9/

Cité par Sources :