Conditions for minimally tough graphs

10/01/2022
by   Clément Dallard, et al.
0

Katona, Soltész, and Varga showed that no induced subgraph can be excluded from the class of minimally tough graphs. In this paper, we consider the opposite question, namely which induced subgraphs, if any, must necessarily be present in each minimally t-tough graph. Katona and Varga showed that for any rational number t ∈ (1/2,1], every minimally t-tough graph contains a hole. We complement this result by showing that for any rational number t>1, every minimally t-tough graph must contain either a hole or an induced subgraph isomorphic to the k-sun for some integer k ≥ 3. We also show that for any rational number t > 1/2, every minimally t-tough graph must contain either an induced 4-cycle, an induced 5-cycle, or two independent edges as an induced subgraph.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset