Geodesic
Lower bound for the size of maximal nontraceable graphs
The electronic journal of combinatorics, Tome 12 (2005)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
Let $g(n)$ denote the minimum number of edges of a maximal nontraceable graph of order $n$. Dudek, Katona and Wojda (2003) showed that $ g(n) \geq \lceil {3n-2\over2} \rceil -2$ for $ n \ge 20$ and $ g(n) \le \lceil {3n-2\over2} \rceil$ for $ n \geq 54$ as well as for $n \in I= \{22,23,30,31,38,39,40,41,42,43,46,$ $47,48,49,50,51\}$. We show that $ g(n) = \lceil {3n-2\over2} \rceil$ for $ n \geq 54$ as well as for $n \in I \cup \{12,13\}$ and we determine $g(n)$ for $n \le 9$.
DOI : 10.37236/1929
Classification : 05C35, 05C45
Mots-clés : Hamiltonian path, traceable 
Marietjie Frick; Joy Singleton. Lower bound for the size of maximal nontraceable graphs. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1929
@article{10_37236_1929,
     author = {Marietjie Frick and Joy Singleton},
     title = {Lower bound for the size of maximal nontraceable graphs},
     journal = {The electronic journal of combinatorics},
     year = {2005},
     volume = {12},
     doi = {10.37236/1929},
     zbl = {1074.05049},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1929/}
}
TY  - JOUR
AU  - Marietjie Frick
AU  - Joy Singleton
TI  - Lower bound for the size of maximal nontraceable graphs
JO  - The electronic journal of combinatorics
PY  - 2005
VL  - 12
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1929/
DO  - 10.37236/1929
ID  - 10_37236_1929
ER  - 
%0 Journal Article
%A Marietjie Frick
%A Joy Singleton
%T Lower bound for the size of maximal nontraceable graphs
%J The electronic journal of combinatorics
%D 2005
%V 12
%U http://geodesic.mathdoc.fr/articles/10.37236/1929/
%R 10.37236/1929
%F 10_37236_1929

Cité par Sources :