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

dmtcs:4514 - Discrete Mathematics & Theoretical Computer Science, November 20, 2018, vol. 20 no. 2
On Almost Well-Covered Graphs of Girth at Least 6

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

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.


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


Share