Toughness and Triangle-Free Graphs

Share/Save/Bookmark

Bauer, D. and Heuvel, J. van den and Schmeichel, E. (1995) Toughness and Triangle-Free Graphs. Journal of Combinatorial Theory, Series B, 65 (2). pp. 208-221. ISSN 0021-9800

open access
[img]
Preview
PDF
532kB
Abstract:In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a relatively complete answer for small values of t.
Item Type:Article
Copyright:© 1995 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/57297
Official URL:http://dx.doi.org/10.1006/jctb.1995.1051
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page