On almost well-covered graphs of girth at least 6

MaRDI QIDQ4560269zbMATH OpenFDO

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

Publication date 10 December 2018

Full work available at URL https://arxiv.org/abs/1708.04632, https://dmtcs.episciences.org/4982/pdf

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)

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.

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₃, C₄, C₅, C₇)-free almost well-dominated graphs
• Publication:4940016

Cited in

(7)

• Extending Berge's and Favaron's results about well-covered graphs
• A characterization of Zm-well-covered graphs of girth 6 or more
• Distinct sizes of maximal independent sets on graphs with restricted girth
• scientific article; zbMATH DE number 5844229 (Why is no real title available?)
• (C₃, C₄, C₅, C₇)-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)