Tınaz Ekim ; Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič - On Almost Well-Covered Graphs of Girth at Least 6

dmtcs:4514 - Discrete Mathematics & Theoretical Computer Science, November 20, 2018, vol. 20 no. 2 - https://doi.org/10.23638/DMTCS-20-2-17
On Almost Well-Covered Graphs of Girth at Least 6Article

Authors: Tınaz Ekim ; Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič

    We consider a relaxation of the concept of well-covered graphs, which are graphs with all maximal independent sets of the same size. The extent to which a graph fails to be well-covered can be measured by its independence gap, defined as the difference between the maximum and minimum sizes of a maximal independent set in $G$. While the well-covered graphs are exactly the graphs of independence gap zero, we investigate in this paper graphs of independence gap one, which we also call almost well-covered graphs. Previous works due to Finbow et al. (1994) and Barbosa et al. (2013) have implications for the structure of almost well-covered graphs of girth at least $k$ for $k\in \{7,8\}$. We focus on almost well-covered graphs of girth at least $6$. We show that every graph in this class has at most two vertices each of which is adjacent to exactly $2$ leaves. We give efficiently testable characterizations of almost well-covered graphs of girth at least $6$ having exactly one or exactly two such vertices. Building on these results, we develop a polynomial-time recognition algorithm of almost well-covered $\{C_3,C_4,C_5,C_7\}$-free graphs.


    Volume: vol. 20 no. 2
    Section: Graph Theory
    Published on: November 20, 2018
    Accepted on: November 2, 2018
    Submitted on: May 18, 2018
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 757 times.
    This article's PDF has been downloaded 378 times.