✦ LIBER ✦

On the complexity of recognizing tough graphs

✍ Scribed by Douglas Bauer; Aurora Morgana; Edward Schmeichel

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 252 KB
Volume: 124
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)00047-u

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the complexity of recognizing perfect

On the complexity of recognizing perfectly orderable graphs

✍ Matthias Middendorf; Frank Pfeiffer 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 365 KB

On the Complexity of Recognizing Hamming

On the Complexity of Recognizing Hamming Graphs and Related Classes of Graphs

✍ Wilfried Imrich; Sandi Klavzar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 287 KB

On the complexity of recognizing a class

On the complexity of recognizing a class of generalized networks

✍ Vijaya Chandru; Collette R Coullard; Donald K Wagner 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 298 KB

On recognizing graphs by numbers of homo

On recognizing graphs by numbers of homomorphisms

✍ Zdeněk Dvořák 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## Abstract Let hom (__G, H__) be the number of homomorphisms from a graph __G__ to a graph __H__. A well‐known result of Lovász states that the function hom (·, __H__) from all graphs uniquely determines the graph __H__ up to isomorphism. We study this function restricted to smaller classes of gra

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.

On the shortness exponent of 1-tough, ma

On the shortness exponent of 1-tough, maximal planar graphs

✍ Michal Tkáč 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 454 KB

It is shown that the shortness exponent of the class of l-tough, maximal planar graphs is at most log, 5. The non-Hamiltonian, l-tough, maximal planar graph with a minimum number of vertices is presented.