2023/10/16 by Leyou Xu, Bo Zhou, Xu, Leyou +1
Computer Science · #Advanced Graph Theory Research #Optimization and Search Problems #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2310.10183
A graph is t-tough if the deletion of any set of, say, m vertices from the graph leaves a graph with at most (m)/(t) components. In 1973, Chvátal suggested the problem of relating toughness to factors in graphs. In 1985, Enomoto et al. showed that each 2-tough graph with at least three vertices has a 2-factor, but for any ε>0, there exists a (2-ε)-tough graph on at least 3 vertices having no 2-factor. In recent years, the study of sufficient conditions for graphs with toughness less than 2 having a 2-factor has received a paramount interest. In this paper, we give new tight sufficient conditions for a t-tough graph having a 2-factor when 1≤ t<2 by involving independence number, minimum degree, connectivity and forbidden forests.