Toughness and edge-toughness (Q1356703): Difference between revisions

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.