Gyula Y. Katona ; Kitti Varga - Minimal toughness in special graph classes

dmtcs:10180 - Discrete Mathematics & Theoretical Computer Science, November 22, 2023, vol. 25:3 special issue ICGT'22 - https://doi.org/10.46298/dmtcs.10180
Minimal toughness in special graph classesArticle

Authors: Gyula Y. Katona ; Kitti Varga

    Let $t$ be a positive real number. A graph is called $t$-tough if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components, and all graphs are considered 0-tough. The toughness of a graph is the largest $t$ for which the graph is $t$-tough, whereby the toughness of complete graphs is defined as infinity. A graph is minimally $t$-tough if the toughness of the graph is $t$, and the deletion of any edge from the graph decreases the toughness. In this paper, we investigate the minimum degree and the recognizability of minimally $t$-tough graphs in the classes of chordal graphs, split graphs, claw-free graphs, and $2K_2$-free graphs.


    Volume: vol. 25:3 special issue ICGT'22
    Section: Special issues
    Published on: November 22, 2023
    Accepted on: October 19, 2023
    Submitted on: October 20, 2022
    Keywords: Mathematics - Combinatorics,05C99

    Consultation statistics

    This page has been seen 590 times.
    This article's PDF has been downloaded 420 times.