Local Structure When All Maximal Independent Sets Have Equal Weight

DOI10.1137/S0895480196300479MaRDI QIDQ4210230zbMATH OpenFDO

Authors Yair Caro, J. E. Ramey, M. N. Ellingham

Publication date 21 September 1998

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480196300479

zbMATH Keywords

characterizationshypergraphhypergraph matchingindependence systemindependent setslocal structurematchingsmaximal independent setpolynomial time algorithmrecognition algorithmweightswell-covered graphwell-covered graphs

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

An \(A\)-weighted graph \(G= (V,E)\) is a graph whose vertices are weighted by elements of an arbitrary abelian group \(A\), and the weight of a given \(S\subseteq V\) is the sum of the weights of its elements. If all maximal independent sets in \(G\) have the same weight, it is called the independence weight of \(G\) and \(G\) is said to be well-covered. In the present paper the authors mention three structures and ask whether all independent sets of them have equal weight. These problems are formulated as follows: (1) Given an \(A\)-weighted graph, is it well-covered? (Graph problem). (2) Given an \(A\)-weighted independence system with all minimal dependent sets of cardinality 2, do all maximal independent sets have the same weight? (Independence system problem). (3) Given an \(A\)-edge-weighted hypergraph, do all maximal matchings have the same weight? (Hypergraph matching problem). Since the authors can show that these three problems are equivalent, it may be asked which is most convenient for a particular application. In this paper the graph problem is investigated. \(G\) can be assumed to be a simple graph. It is known that this problem is co-NP-complete in general. In Section 2 well-covered \(A\)-weighted graphs are characterized. The notion of a minimal non-well-covered graph is introduced and some of its characterizations are given (Theorem 2.3, Corollaries 2.4 and 2.5). In Section 3 these corollaries are used to prove that well-coveredness depends on the local, rather than the global, structure of \(G\). Basing on these results, the authors develop an algorithm to recognize well-covered graphs and they show that for graphs with \(n\) vertices and maximum degree \(\Delta\), it runs in linear time if \(\Delta\) is bounded by a constant, and in polynomial time if \(\Delta= O(\root 4\of{\log n})\) (see Corollary 3.3). Some applications of their results on areas which include hypergraph matchings and certain independent sets are also mentioned. In the last section, Section 4, the authors are concerned with the problem of determining whether a graph has a weighting which makes it well-covered.

Recommendations

• Weighted well-covered claw-free graphs
• The structure of well-covered graphs with no cycles of length 4
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
• The structure of well-covered graphs and the complexity of their recognition problems

Cited in

(32)

• The uniformity space of hypergraphs and its applications
• The structure of well-covered graphs and the complexity of their recognition problems
• Graphs vertex-partitionable into strong cliques
• Weighted well-covered graphs without cycles of lengths 5, 6 and 7
• Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7
• On the structure of 4-regular planar well-covered graphs
• Detecting strong cliques
• Well-covered graphs without cycles of lengths 4, 5 and 6
• Well-dominated graphs without cycles of lengths 4 and 5
• On relating edges in graphs without cycles of length 4
• Minimal invariant sets in a vertex-weighted graph
• The structure of well-covered graphs with no cycles of length 4
• On unique independence weighted graphs
• Well-covered triangulations. IV
• Graphs with maximal induced matchings of the same size
• On related edges in well-covered graphs without cycles of length 4 and 6
• Extending Berge's and Favaron's results about well-covered graphs
• Constructions for well-covered graphs
• The well-covered dimension of products of graphs
• scientific article; zbMATH DE number 4122023 (Why is no real title available?)
• Weighted well-covered claw-free graphs
• A characterization of Zm-well-covered graphs of girth 6 or more
• On well-covered pentagonalizations of the plane
• Recognizing generating subgraphs revisited
• Computing well-covered vector spaces of graphs using modular decomposition
• Well-covered graphs with constraints on \(\Delta\) and \(\delta\)
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
• Recognizing relating edges in graphs without cycles of length 6
• Beyond recognizing well-covered graphs
• Generating subgraphs in chordal graphs
• Complexity results for generating subgraphs
• The well-covered dimension of random graphs

This page was built for publication: Local Structure When All Maximal Independent Sets Have Equal Weight

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