3
$\begingroup$

We say that a graph is t-tough if by deleting a set if vertices $S$, the resulting graph will have at most $|S|/t$ connected components. We say that a graph is minimally t-tough if the deletion of an edge results in a non-t-tough graph. It is conjectured by Kriessel that every minimally $1$-tough graph has a vertex of order two (see http://iti.zcu.cz/history/2003/Hajek/problems/hajek-problems.ps). In other words, in minimally $1$-tough graphs, there is a local reason for not being tougher. (Deleting the endpoints of a vertex of order two results in two components, demonstrating that the graph is at most $1$-tough.) In the spirit of Kriessel's conjecture I have the following (hopefully easier) question.

Question: Is it true that there exists $ \varepsilon >0 $ such that any minimally $\varepsilon$-tough graph has a vertex of degree $1$?

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm still getting my head around the definition. Anyway, take m = 1/epsilon many disjoint cycle graphs of diameter > 2 , and pick a point on each cycle and identify all those m points to get an m petalled flower graph. Does this help with the question? (I'm unsure if it is minimal.) $\endgroup$
    – The Masked Avenger
    Commented Jul 4, 2015 at 23:37
  • $\begingroup$ It is indeed not minimal, you can delete an edge of the identified point and the resulting graph is still $m$-tough. The minimally $m$-tough subgraph in your graph is a star-like tree but with longer paths instead of the leaves. $\endgroup$
    – Daniel Soltész
    Commented Jul 5, 2015 at 0:46

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .