Premium
Various results on the toughness of graphs
Author(s) -
Broersma Hajo,
Engbers Erik,
Trommel Huib
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199905)33:3<233::aid-net9>3.0.co;2-a
Subject(s) - combinatorics , mathematics , toughness , graph , vertex connectivity , discrete mathematics , materials science , composite material , vertex (graph theory)
Let G be a graph and let t ≥ 0 be a real number. Then, G is t ‐tough if t ω( G − S ) ≤ | S | for all S ⊆ V ( G ) with ω( G − S ) > 1, where ω( G − S ) denotes the number of components of G − S . The toughness of G , denoted by τ( G ), is the maximum value of t for which G is t ‐tough [taking τ( K n ) = ∞ for all n ≥ 1]. G is minimally t ‐tough if τ( G ) = t and τ( H ) < t for every proper spanning subgraph H of G . We discuss how the toughness of (spanning) subgraphs of G and related graphs depends on τ( G ), we give some sufficient degree conditions implying that τ( G ) ≥ t , and we study which subdivisions of 2‐connected graphs have minimally 2‐tough squares. © 1999 John Wiley & Sons, Inc. Networks 33: 233–238, 1999