Toughness and edge-toughness
type: Item
instance of: scholarly article
title: Toughness and edge-toughness
zbMATH Open document ID: 0874.05035
DOI: 10.1016/S0012-365X(96)00051-9
author: Gyula Y. Katona
published in: Discrete Mathematics
publication date: 1997-11-09T00:00:00Z
review text: The toughness of a graph \(G\), introduced by \textit{V. Chvátal} [Discrete Math. 5, 215-228 (1973; Zbl 0256.05122)] in studying hamiltonicity, is the largest real number \(t\) for which \(|S|\geq t\omega (G-S)\) for every \(S\subseteq V(G)\) with \(\omega (G-S)\geq 2\). Chvátal conjectured the existence of a constant \(t_0\) such that every \(t_0\)-tough graph is hamiltonian. The author shows how this motivates the following definition of edge-toughness. Given a collection \(A\) of vertices, the pair \((X,Y)\), where \(X\subseteq V(G-A)\) and \(Y\subseteq E(G-A-X)\), disconnects \(A\) if \(G-X-Y\) has no path connecting two vertices of \(A\). Let \(Q_1,Q_2, \dots, Q_n\) be the components of the edge induced subgraph \(G(Y)\). Set \(\text{bd}_{G-X} (Q_i)= \{v\in V(Q_i) \mid v\) has a neighbor outside of \(Q_i\) and \(X\}\) and \(\text{in}_{G-X} (Q_i)= V(Q_i)- \text{bd}_{G-X} (Q_i)\). The edge-toughness of \(G\) is the largest real number \(t\) for which \[ |X|+ \sum^n_{i=1} \biggl\lfloor \bigl|\text{bd}_{G-X} (Q_i)\bigr |/2 \biggr\rfloor \geq t\omega \left(G-X-Y- \bigcup^n_{i=1} \text{in}_{G-X} (Q_i) \right) \] holds for every \(X\subseteq V(G)\) and \(Y\subseteq E(G-X)\) satisfying \[ \omega \left(G-X-Y- \bigcup^n_{i=1} \text{in}_{G-X} (Q_i) \right)>1. \] It is shown that if \(G\) is \(2t\)-tough then it is \(t\)-edge-tough and conjectured that the converse holds for no \(t\). Several other interesting relations between toughness and edge-toughness are conjectured.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1019062
zbMATH Keywords: toughness
zbMATH Keywords: hamiltonicity
zbMATH Keywords: hamiltonian
zbMATH Keywords: edge-toughness
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Long cycles in graphs with prescribed toughness and minimum degree
cites work: Q4871126
cites work: Q3139757
cites work: Tough graphs and Hamiltonian circuits.
cites work: Toughness and the existence ofk-factors
cites work: Q3972952
cites work: Über die Maximalzahl kreuzungsfreier H-Wege
full work available at URL: s0012-365x(96)00051-9
OpenAlex ID: W2011648561
Recommended article: Chvátal’s t 0-Tough Conjecture
Recommended article: Toughness, minimum degree, and the existence of 2‐factors
Recommended article: A Remark on Hamiltonian Cycles
Recommended article: Q3139757
Recommended article: On hamiltonicity of 1-tough triangle-free graphs
Recommended article: Tough graphs and Hamiltonian circuits.
Recommended article: On Toughness and Hamiltonicity of 2K2‐Free Graphs
Recommended article: Q4871058
Recommended article: A sufficient condition for Hamiltonian cycles in tough graphs
Recommended article: Toughness, hamiltonicity and split graphs
description: scientific article; zbMATH DE number 1019062