Geodesic
Lower bound for the size of maximal nontraceable graphs
The electronic journal of combinatorics, Tome 12 (2005)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :