Conditions for minimally tough graphs

Clément, Dallard and Blas, Fernández and Katona, Gyula Y. and Milanič, Martin and Varga, Kitti Katalin (2022) Conditions for minimally tough graphs. JOURNAL OF GRAPH THEORY, Submit. ISSN 0364-9024

Preview

Text 2210.00383.pdf Download (234kB) | Preview

Abstract

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.

Actions (login required)

Edit Item