Geodesic
Maximal nontraceable graphs with toughness less than one
The electronic journal of combinatorics, Tome 15 (2008)

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

Zbl EuDML
A graph $G$ is maximal nontraceable (MNT) if $G$ does not have a hamiltonian path but, for every $e\in E\left( \overline{G}\right) $, the graph $G+e$ has a hamiltonian path. A graph $G$ is 1-tough if for every vertex cut $S$ of $G$ the number of components of $G-S$ is at most $|S|$. We investigate the structure of MNT graphs that are not 1-tough. Our results enable us to construct several interesting new classes of MNT graphs.
DOI : 10.37236/742
Classification : 05C38, 05C45
Mots-clés : maximal nontraceable graph, MNT, Hamiltonian path;tough graphs 
Frank Bullock; Marietjie Frick; Joy Singleton; Susan van Aardt; Kieka (C.M.) Mynhardt. Maximal nontraceable graphs with toughness less than one. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/742
@article{10_37236_742,
     author = {Frank Bullock and Marietjie Frick and Joy Singleton and Susan van Aardt and Kieka (C.M.) Mynhardt},
     title = {Maximal nontraceable graphs with toughness less than one},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/742},
     zbl = {1180.05056},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/742/}
}
TY  - JOUR
AU  - Frank Bullock
AU  - Marietjie Frick
AU  - Joy Singleton
AU  - Susan van Aardt
AU  - Kieka (C.M.) Mynhardt
TI  - Maximal nontraceable graphs with toughness less than one
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/742/
DO  - 10.37236/742
ID  - 10_37236_742
ER  - 
%0 Journal Article
%A Frank Bullock
%A Marietjie Frick
%A Joy Singleton
%A Susan van Aardt
%A Kieka (C.M.) Mynhardt
%T Maximal nontraceable graphs with toughness less than one
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/742/
%R 10.37236/742
%F 10_37236_742

Cité par Sources :