Recognizing Generating Subgraphs Revisited

DOI10.1142/S0129054121500052zbMath1458.68142arXiv1811.04433OpenAlexW3133005159MaRDI QIDQ5859675

David Tankus, Vadim E. Levit

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

vector spacemaximal independent setgenerating subgraphweighted well-covered graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Well-covered graphs with constraints on \(\Delta\) and \(\delta\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted well-covered claw-free graphs
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
• Complexity results for generating subgraphs
• A characterization of well covered graphs of girth 5 or greater
• The structure of well-covered graphs and the complexity of their recognition problems
• Well-covered claw-free graphs
• Well-covered graphs without cycles of lengths 4, 5 and 6
• On relating edges in graphs without cycles of length 4
• The structure of well-covered graphs with no cycles of length 4
• Complexity results for well‐covered graphs
• Complexity of automaton identification from given data
• Local Structure When All Maximal Independent Sets Have Equal Weight
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Recognizing Greedy Structures
• Well covered simplicial, chordal, and circular arc graphs
• Well-Covered Vector Spaces of Graphs
• Some covering concepts in graphs

This page was built for publication: Recognizing Generating Subgraphs Revisited