Back to Search
Start Over
Disproof of a conjecture on minimally t-tough graphs.
- Source :
-
Discrete Mathematics . Jul2024, Vol. 347 Issue 7, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- Let G be a graph and let ω (G) denote the number of components of G. The graph G is said to be t-tough if t ⋅ ω (G − X) ≤ | X | for all X ⊆ V (G) with ω (G − X) > 1 , where t is a nonnegative real number. The toughness τ (G) of the graph G is the maximum value of t such that G is t -tough (taking τ (K n) = ∞ for all n ≥ 1). A graph G is said to be minimally t-tough if τ (G) = t and τ (G − e) < t for every e ∈ E (G). Kriesell (2003) conjectured that every minimally 1-tough graph has a vertex of degree 2. Katona and Varga (2018) proposed a generalized version that every minimally t -tough graph has a vertex of degree ⌈ 2 t ⌉ for any positive real number t. In this note, we disprove the Generalized Kriesell's Conjecture by constructing an infinite family of counterexamples having toughness close to 1, and thus also show that the toughness condition in Kriesell's Conjecture would be sharp. [ABSTRACT FROM AUTHOR]
- Subjects :
- *LOGICAL prediction
*REAL numbers
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 347
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 177223968
- Full Text :
- https://doi.org/10.1016/j.disc.2024.113982