Treffer: Toughness and hamiltonicity in k-trees

Title:
Toughness and hamiltonicity in k-trees
Authors:
BROERSMA, Hajo, LIMING XIONG, YOSHIMOTO, Kiyoshi
Source:
Cycles and colourings 2003Discrete mathematics. 307(7-8):832-838
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 17 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Arbre, Tree, Arbol, Complexité, Complexity, Complejidad, Condition existence, Existence condition, Condición existencia, Condition nécessaire, Necessary condition, Condición necesaria, Cycle hamiltonien, Hamiltonian cycle, Ciclo hamiltoniano, Graphe hamiltonien, Hamiltonian graph, Grafo hamiltoniano, Graphe triangulé, Chordal graph, Grafo triangular, Coriacité, Toughness, Graphe cordal, Graphique décelable, Traceable graph, 05C35, 05C45, Traceable graph: Chordal graph, k-tree, t-tough graph
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Centerfor Combinatorics, Nakai University, Tianjin 300071, China
Department of Computer Science, University of Durham, South Road, DH1 3LE Durham, United Kingdom
Department of Mathematics, Beijing Institute of Technology, Beijing 100081, China
Department of Mathematics, Jiangxi Normal University, Nanchang 330027, China
Department of Mathematics, College of Science and Technology, Nihon University, 1-8 Kanda-Surugadai, Chiyoda-ku, Tokyo 101-8308, Japan
ISSN:
0012-365X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18531346
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Mathematics
Accession Number:
edscal.18531346
Database:
PASCAL Archive

Weitere Informationen

We consider toughness conditions that guarantee the existence of a hamiltonian cycle in k-trees, a subclass of the class of chordal graphs. By a result of Chen et al. 18-tough chordal graphs are hamiltonian, and by a result of Bauer et al. there exist nontraceable chordal graphs with toughness arbitrarily close to 7/4. It is believed that the best possible value of the toughness guaranteeing hamiltonicity of chordal graphs is less than 18, but the proof of Chen et al. indicates that proving a better result could be very complicated. We show that every 1-tough 2-tree on at least three vertices is hamiltonian, a best possible result since 1-toughness is a necessary condition for hamiltonicity. We generalize the result to k-trees for k ≥ 2: Let G be a k-tree. If G has toughness at least (k + 1)/3, then G is hamiltonian. Moreover, we present infinite classes of nonhamiltonian 1-tough k-trees for each k ≥ 3.