✦ LIBER ✦

The toughness of split graphs

✍ Scribed by Gerhard J. Woeginger

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 117 KB
Volume: 190
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00156-3

No coin nor oath required. For personal study only.

✦ Synopsis

In this short note we argue that the toughness of split graphs can be computed in polynomial time.

📜 SIMILAR VOLUMES

Toughness, hamiltonicity and split graph

Toughness, hamiltonicity and split graphs

✍ Dieter Kratsch; Jenő Lehel; Haiko Müller 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 728 KB

Split dimension of graphs

✍ Arkady A. Chernyak; Zhanna A. Chernyak 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 380 KB

## Chernyak, A.A. and Z.A. Chernyak, Split dimension of graphs, Discrete Mathematics 89 (1991) l-6.

Various results on the toughness of grap

Various results on the toughness of graphs

✍ Broersma, Hajo; Engbers, Erik; Trommel, Huib 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views

Let G be a graph and let t Ն 0 be a real number. Then, 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.

Endomorphism—Regularity of Split Graphs

✍ Weimin Li; Jianfei Chen 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 126 KB

In this paper, split graphs with a regular endomorphism monoid are characterized explicitly.

Absolute retracts of split graphs

✍ Sandi Klavžar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 663 KB

It is proved that a split graph is an absolute retract of split graphs if and only if a partition of its vertex set into a stable set and a complete set is unique or it is a complete split graph. Three equivalent conditions for a split graph to be an absolute retract of the class of all graphs are g

On the complexity of recognizing tough g

On the complexity of recognizing tough graphs

✍ Douglas Bauer; Aurora Morgana; Edward Schmeichel 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 252 KB