ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Computing well-covered vector spaces of graphs using modular decomposition
    Milanič, Martin, 1980- ; Pivač, Nevena
    A graph is well-covered if all its maximal independent sets have the same cardinality. This concept was introduced by Plummer in 1970 and naturally generalizes to the weighted case. Given a graph G, ... a real-valued vertex weight function w is said to be a well-covered weighting of G if all its maximal independent sets are of the same weight with respect to w. The set of all well-covered weightings of a graph G forms a vector space over the field of real numbers, called the well-covered vector space of G. Since the problem of recognizing well-covered graphs is - -complete, the problem of computing the well-covered vector space of a given graph is - -hard. Levit and Tankus showed in 2015 that the problem admits a polynomial-time algorithm in the class of claw-free graphs. In this paper, we give two general reductions for the problem, one based on anti-neighborhoods and one based on modular decomposition, combined with Gaussian elimination. Building on these results, we develop a polynomial-time algorithm for computing the well-covered vector space of a given fork-free graph, generalizing the result of Levit and Tankus. Our approach implies a polynomial-time recognition algorithm for the class of well-covered fork-free graphs and also generalizes some known results on cographs.
    Source: Computational & Applied Mathematics. - ISSN 2238-3603 (Vol. 42, art. 360, 2023, str. 1-23)
    Type of material - article, component part ; adult, serious
    Publish date - 2023
    Language - english
    COBISS.SI-ID - 173648387

    Link(s):

    https://link.springer.com/article/10.1007/s40314-023-02502-8#citeas
    https://doi.org/10.1007/s40314-023-02502-8
    DOI

Shelf entry