Abstract: A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space. Given an input claw-free graph G, we present an O(n^6)algortihm, whose input is a claw-free graph G, and output is the vector space of weight functions w, for which G is w-well-covered. A graph G is equimatchable if all its maximal matchings are of the same cardinality. Assume that a weight function w is defined on the edges of G. Then G is w-equimatchable if all its maximal matchings are of the same weight. For every graph G, the set of weight functions w such that G is w-equimatchable is a vector space. We present an O(m*n^4 + n^5*log(n)) algorithm which receives an input graph G, and outputs the vector space of weight functions w such that G is w-equimatchable.
Recommendations
- Well-covered claw-free graphs
- Minimum weighted clique cover on claw‐free perfect graphs
- Clique coverings and claw-free graphs
- Claw conditions for heavy cycles in weighted graphs
- On 4-connected claw-free well-covered graphs
- scientific article; zbMATH DE number 3893237
- Edge clique cover of claw-free graphs
- On weighted clique graphs
- Almost claw‐free graphs
- Claw-free graphs with complete closure
Cites work
- Q3138921 scientific article; zbMATH DE number 432790 (Why is no real title available?)
- Q3139761 scientific article; zbMATH DE number 434906 (Why is no real title available?)
- Q3340896 scientific article; zbMATH DE number 3873377 (Why is no real title available?)
- Q4179024 scientific article; zbMATH DE number 3614795 (Why is no real title available?)
- Q5365068 scientific article; zbMATH DE number 6783420 (Why is no real title available?)
- A characterization of well covered graphs of girth 5 or greater
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- Complexity results for well‐covered graphs
- Efficient recognition of equimatchable graphs
- Finding and counting small induced subgraphs efficiently
- Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests
- Local Structure When All Maximal Independent Sets Have Equal Weight
- On maximal independent sets of vertices in claw-free graphs
- On related edges in well-covered graphs without cycles of length 4 and 6
- On relating edges in graphs without cycles of length 4
- Recognizing Greedy Structures
- The structure of well-covered graphs and the complexity of their recognition problems
- The structure of well-covered graphs with no cycles of length 4
- Very well covered graphs
- WELL-COVERED GRAPHS: A SURVEY
- Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
- Well covered simplicial, chordal, and circular arc graphs
- Well-covered claw-free graphs
- Well-covered graphs without cycles of lengths 4, 5 and 6
Cited in
(10)- Partitions and well-coveredness: the graph sandwich problem
- Weighted well-covered graphs without cycles of lengths 5, 6 and 7
- Recognizing generating subgraphs revisited
- Equimatchable claw-free graphs
- Computing well-covered vector spaces of graphs using modular decomposition
- Well-covered graphs with constraints on \(\Delta\) and \(\delta\)
- Well-dominated graphs without cycles of lengths 4 and 5
- Recognizing \(\text{W}_2\) graphs
- Complexity results for generating subgraphs
- Well-covered graphs without cycles of lengths 4, 5 and 6
This page was built for publication: Weighted well-covered claw-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482209)
