Various results on the toughness of graphs
| Autor: | Erik Engbers, H. Trommel, Haitze J. Broersma |
|---|---|
| Přispěvatelé: | Discrete Mathematics and Mathematical Programming |
| Rok vydání: | 1999 |
| Předmět: |
Discrete mathematics
Toughness Spanning subgraph Computer Networks and Communications degree sum condition Hamiltonian path IR-71525 Graph Combinatorics toughness (of subgraphs) symbols.namesake square of a graph Subgroup Hardware and Architecture minimally t-tough graph symbols t-Tough graph METIS-140564 Software Connectivity Information Systems Mathematics Real number |
| Zdroj: | Networks, 33(33), 233-238. Wiley-Liss Inc. University of Twente Research Information (Pure Portal) |
| ISSN: | 0028-3045 |
| Popis: | Let G be a graph, and let t 0 be a real number. Then G is t-tough if t!(G − S) jSj 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 (Kn) = 1 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 sucient (degree) conditions implying (G) t, and we study which subdivisions of 2-connected graphs have minimally 2-tough squares. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text