×

On a connection between the existence of k-trees and the toughness of a graph. (English) Zbl 0673.05054

Summary: A graph G has toughness t(G) if t(G) is the largest number t such that for any subset S of the vertices of G, the number of vertices in S is at least t times the number of components of G on deletion of the vertices in S, provided that there is then more than one component. A k-tree of a connected graph is a spanning tree with maximum degree at most k. We show here that if \(t(G)\geq 1/(k-2),\) with \(k\geq 3\), ten G has a k-tree. The notion of a k-tree generalizes the case \(k=2\) of a Hamiltonian path, so that this result, as we discuss, may be of some interest in connection with Chvátal’s conjecture that, for some t, every graph with toughness at least t is Hamiltonian.

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chvátal, V.: Tough graphs and hamiltonian circuits. Discrete Math.5, 215–228 (1973) · Zbl 0256.05122 · doi:10.1016/0012-365X(73)90138-6
[2] Matthews, M.M., Sumner, D.P.: Hamiltonian results inK 1, 3-free graphs. J. Graph Theory8, 139–146 (1984) · Zbl 0536.05047 · doi:10.1002/jgt.3190080116
[3] Win, Sein: Über Gerüste mit vorgeschriebenen Maximalgraden in Graphen und eine Vermutung von Las Vergnas. Ph.D. Thesis, Universität Hamburg (1979) · Zbl 0477.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.