Local Structure When All Maximal Independent Sets Have Equal Weight

DOI10.1137/S0895480196300479zbMath0914.05061MaRDI QIDQ4210230

J. E. Ramey, Yair Caro, Mark N. Ellingham

Publication date: 21 September 1998

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

zbMATH Keywords

weightshypergraphcharacterizationspolynomial time algorithmmatchingsindependent setsindependence systemlocal structuremaximal independent sethypergraph matchingwell-covered graphrecognition algorithmwell-covered graphs

Mathematics Subject Classification ID

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

Related Items (25)

Well-covered triangulations. IV ⋮ The structure of well-covered graphs with no cycles of length 4 ⋮ Graphs with maximal induced matchings of the same size ⋮ The well-covered dimension of random graphs ⋮ Well-dominated graphs without cycles of lengths 4 and 5 ⋮ A characterization of Zm-well-covered graphs of girth 6 or more ⋮ Extending Berge's and Favaron's results about well-covered graphs ⋮ Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7 ⋮ On the structure of 4-regular planar well-covered graphs ⋮ Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\) ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Well-covered graphs with constraints on \(\Delta\) and \(\delta\) ⋮ Graphs vertex-partitionable into strong cliques ⋮ On relating edges in graphs without cycles of length 4 ⋮ The well-covered dimension of products of graphs ⋮ Weighted well-covered claw-free graphs ⋮ On well-covered pentagonalizations of the plane ⋮ Complexity results for generating subgraphs ⋮ Weighted well-covered graphs without cycles of lengths 5, 6 and 7 ⋮ Detecting strong cliques ⋮ On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6 ⋮ Unnamed Item ⋮ The uniformity space of hypergraphs and its applications ⋮ Recognizing Generating Subgraphs Revisited ⋮ Well-covered graphs without cycles of lengths 4, 5 and 6

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