On almost well-covered graphs of girth at least 6

zbMATH Open1401.05232arXiv1708.04632MaRDI QIDQ4560269FDOQ4560269

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

Publication date: 10 December 2018

Abstract: 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 $kin7,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.

Full work available at URL: https://arxiv.org/abs/1708.04632

Recommendations

• A characterization of well covered graphs of girth 5 or greater
• scientific article; zbMATH DE number 1308945
• scientific article; zbMATH DE number 1409193
• \((C_3, C_4, C_5, C_7)\)-free almost well-dominated graphs
• Publication:4940016

zbMATH Keywords

girthmaximal independent setalmost well-covered graphindependence gap

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (6)

• A characterization of Zm-well-covered graphs of girth 6 or more
• Distinct sizes of maximal independent sets on graphs with restricted girth
• Title not available (Why is that?)
• \((C_3, C_4, C_5, C_7)\)-free almost well-dominated graphs
• Mind the independence gap
• Well-indumatched Trees and Graphs of Bounded Girth

This page was built for publication: On almost well-covered graphs of girth at least 6

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4560269)