Weighted well-covered claw-free graphs

DOI10.1016/J.DISC.2014.10.008zbMATH Open1305.05176arXiv1312.7563OpenAlexW2962759348MaRDI QIDQ482209FDOQ482209

Authors: Vadim E. Levit, David Tankus 

Publication date: 19 December 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

claw-free graphmaximal independent setwell-covered graphequimatchable graphmaximal matching

Mathematics Subject Classification ID

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

Cites Work

• A characterization of well covered graphs of girth 5 or greater
• WELL-COVERED GRAPHS: A SURVEY
• Title not available (Why is that?)
• On maximal independent sets of vertices in claw-free graphs
• Well-covered claw-free graphs
• Title not available (Why is that?)
• Recognizing Greedy Structures
• Title not available (Why is that?)
• Finding and counting small induced subgraphs efficiently
• The structure of well-covered graphs and the complexity of their recognition problems
• Very well covered graphs
• Complexity results for well‐covered graphs
• Local Structure When All Maximal Independent Sets Have Equal Weight
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Title not available (Why is that?)
• Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests
• On related edges in well-covered graphs without cycles of length 4 and 6
• Well covered simplicial, chordal, and circular arc graphs
• The structure of well-covered graphs with no cycles of length 4
• Well-covered graphs without cycles of lengths 4, 5 and 6
• Efficient recognition of equimatchable graphs
• On relating edges in graphs without cycles of length 4
• Title not available (Why is that?)
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)

Cited In (10)

• Partitions and well-coveredness: the graph sandwich problem
• Well-covered graphs without cycles of lengths 4, 5 and 6
• Recognizing \(\text{W}_2\) graphs
• Complexity results for generating subgraphs
• Computing well-covered vector spaces of graphs using modular decomposition
• Well-covered graphs with constraints on \(\Delta\) and \(\delta\)
• Equimatchable claw-free graphs
• Well-dominated graphs without cycles of lengths 4 and 5
• Weighted well-covered graphs without cycles of lengths 5, 6 and 7
• Recognizing generating subgraphs revisited

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)