Premium
On the toughness index of planar graphs
Author(s) -
Dillencourt Michael B.
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180110
Subject(s) - combinatorics , planar graph , mathematics , outerplanar graph , discrete mathematics , graph power , graph , wheel graph , 1 planar graph , chordal graph , pathwidth , line graph
Abstract The toughness indexτ ( G ) of a graph G is defined to be the largest integer t such that for any S ⊆ V ( G ) with | S | > t , c ( G ‐ S ) < | S | ‐ t , where c ( G ‐ S ) denotes the number of components of G ‐ S . In particular, 1‐tough graphs are exactly those graphs for which τ( G ) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ( G ) ≥ 2 if and only if G is 4‐connected. This result suggests that there may be a polynomial‐time algorithm for determining whether a planar graph is 1‐tough, even though the problem for general graphs is NP‐hard. The result can be restated as follows: a planar graph is 4‐connected if and only if it remains 1‐tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4‐connected planar graph yields a Hamiltonian graph.