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 2K2-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

    Classifications

    Consultation statistics

    This page has been seen 816 times.
    This article's PDF has been downloaded 539 times.