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
We now know that not every $2$-tough graph is hamiltonian. In fact for every $\epsilon > 0$, there e...
AbstractThe toughness of a graph G is defined as the largest real number t such that deletion of any...
We now know that not every 2-tough graph is hamiltonian. In fact for every ϵ > 0, there exists a (9/...
AbstractIn this paper, we prove that there exist triangle-free graphs with arbitrarily large toughne...
Let $t$ be a positive real number. A graph is called $t$-tough if the removalof any vertex set $S$ t...
We show that it is NP-hard to determine if a cubic graph G is 1-tough. We then use this result to sh...
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A...
A simplified version of the theory of strongly regular graphs is developed for the case in which the...
Let ω(G) denote the number of components of a graph G. A connected graph G is said to be 1-tough if ...
this paper only finite, undirected and simple graphs are considered. In 1973 Chv'atal [4] intro...
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) w...
In this survey we have attempted to bring together most of the results and papers that deal with tou...
AbstractWe consider the relationship between the minimum degree δ of a graph and the complexity of r...
AbstractA graph G is called triangle-free if G has no induced K3 as a subgraph. We set σ3=min{∑i=13d...
We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is ...
We now know that not every $2$-tough graph is hamiltonian. In fact for every $\epsilon > 0$, there e...
AbstractThe toughness of a graph G is defined as the largest real number t such that deletion of any...
We now know that not every 2-tough graph is hamiltonian. In fact for every ϵ > 0, there exists a (9/...
AbstractIn this paper, we prove that there exist triangle-free graphs with arbitrarily large toughne...
Let $t$ be a positive real number. A graph is called $t$-tough if the removalof any vertex set $S$ t...
We show that it is NP-hard to determine if a cubic graph G is 1-tough. We then use this result to sh...
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A...
A simplified version of the theory of strongly regular graphs is developed for the case in which the...
Let ω(G) denote the number of components of a graph G. A connected graph G is said to be 1-tough if ...
this paper only finite, undirected and simple graphs are considered. In 1973 Chv'atal [4] intro...
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) w...
In this survey we have attempted to bring together most of the results and papers that deal with tou...
AbstractWe consider the relationship between the minimum degree δ of a graph and the complexity of r...
AbstractA graph G is called triangle-free if G has no induced K3 as a subgraph. We set σ3=min{∑i=13d...
We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is ...
We now know that not every $2$-tough graph is hamiltonian. In fact for every $\epsilon > 0$, there e...
AbstractThe toughness of a graph G is defined as the largest real number t such that deletion of any...
We now know that not every 2-tough graph is hamiltonian. In fact for every ϵ > 0, there exists a (9/...
DOI
Add to ORKG