Various results on the toughness of graphs

Haitze J. Broersma, E.A. Engbers, H. Trommel

Research output: Book/ReportReportProfessional

36 Downloads (Pure)

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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages14
ISBN (Print)0169-2690
Publication statusPublished - 1997

Publication series

NameMemorandum / University of Twente, Faculty of Applied Mathematics
PublisherUniversiteit Twente
No.1372

Keywords

  • METIS-141163
  • IR-30523

Cite this

Broersma, H. J., Engbers, E. A., & Trommel, H. (1997). Various results on the toughness of graphs. (Memorandum / University of Twente, Faculty of Applied Mathematics; No. 1372). Enschede: Universiteit Twente.
Broersma, Haitze J. ; Engbers, E.A. ; Trommel, H. / Various results on the toughness of graphs. Enschede : Universiteit Twente, 1997. 14 p. (Memorandum / University of Twente, Faculty of Applied Mathematics; 1372).
@book{d65286c1bceb49f7854beec0b7dfe864,
title = "Various results on the toughness of graphs",
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.",
keywords = "METIS-141163, IR-30523",
author = "Broersma, {Haitze J.} and E.A. Engbers and H. Trommel",
note = "Memorandum fac. TW nr 1372",
year = "1997",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum / University of Twente, Faculty of Applied Mathematics",
publisher = "Universiteit Twente",
number = "1372",

}

Broersma, HJ, Engbers, EA & Trommel, H 1997, Various results on the toughness of graphs. Memorandum / University of Twente, Faculty of Applied Mathematics, no. 1372, Universiteit Twente, Enschede.

Various results on the toughness of graphs. / Broersma, Haitze J.; Engbers, E.A.; Trommel, H.

Enschede : Universiteit Twente, 1997. 14 p. (Memorandum / University of Twente, Faculty of Applied Mathematics; No. 1372).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Various results on the toughness of graphs

AU - Broersma, Haitze J.

AU - Engbers, E.A.

AU - Trommel, H.

N1 - Memorandum fac. TW nr 1372

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - METIS-141163

KW - IR-30523

M3 - Report

SN - 0169-2690

T3 - Memorandum / University of Twente, Faculty of Applied Mathematics

BT - Various results on the toughness of graphs

PB - Universiteit Twente

CY - Enschede

ER -

Broersma HJ, Engbers EA, Trommel H. Various results on the toughness of graphs. Enschede: Universiteit Twente, 1997. 14 p. (Memorandum / University of Twente, Faculty of Applied Mathematics; 1372).