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$?

$\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$ 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$ Jul 5, 2015 at 0:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.