Back to University of Twente portal
Various results on the toughness of graphs
Broersma, H.J. and Engbers, E.A. and Trommel, H. (1997) Various results on the toughness of graphs. [Report]
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 155Kb |
| Abstract: | 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. |
| Item Type: | Report |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/30523 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 141163