The toughness of cubic graphs (Q1911237)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The toughness of cubic graphs |
scientific article |
Statements
The toughness of cubic graphs (English)
0 references
29 September 1996
0 references
If \(k(G)\) denotes the number of components of a graph \(G\), the toughness \(\tau(G)\) is defined as the minimum of \(|S|/k(G- S)\) taken over all sets \(S\) of vertices such that \(k(G- S)\geq 2\). New upper bounds for \(\tau(G)\) are presented for noncomplete cubic graphs on \(n\) vertices. In particular, it is shown that \(\tau(G)\leq \min\{(2n- 3\beta)/(n- \beta), 2\beta/(4\beta- n)\}\), where \(\beta\) is the independence number of \(G\). Another result is that \(\tau(G)\leq n/(n- a)\), where \(a\) is the minimum number of vertices whose removal from \(G\) leaves a bipartite graph. For a cycle permutation graph \(G\) satisfying a certain condition it is shown that \(\tau(G)\leq 4/3+ 4/(9m- 3)\), thus supporting a conjecture that the toughness of such graphs does not exceed 4/3.
0 references
toughness
0 references
cubic graphs
0 references
independence number
0 references
cycle permutation graph
0 references