Graphs with maximal induced matchings of the same size

DOI10.1016/J.DAM.2016.08.015MaRDI QIDQ344824zbMATHOpenAlexWikidataFDO

Authors Philippe Baptiste, M. Y. Kovalyov, Yury L. Orlovich, Frank Werner, I.È. Zverovich

Publication date 24 November 2016

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

Full work available at URL https://doi.org/10.1016/j.dam.2016.08.015

zbMATH Keywords

computational complexityinduced matchingwell-covered graphoptimization problemforbidden induced subgraph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A characterization of well-indumatchable graphs having girth greater than seven
• Well-indumatched Trees and Graphs of Bounded Girth
• The structure of well-covered graphs and the complexity of their recognition problems
• Independent domination and matchings in graphs
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size

Cites work

• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 3873377 (Why is no real title available?)
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3614795 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 205349 (Why is no real title available?)
• scientific article; zbMATH DE number 3286813 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A characterization of well covered graphs of girth 5 or greater
• A characterization of well-covered graphs in terms of forbidden costable subgraphs
• A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem
• Approximability results for the maximum and minimum maximal induced matching problems
• Bipartite Domination and Simultaneous Matroid Covers
• Complexity results for well‐covered graphs
• Computing the Minimum Fill-In is NP-Complete
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• Dominating sets for split and bipartite graphs
• Equipackable graphs
• Finding a maximum induced matching in weakly chordal graphs
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Graph theory
• Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests
• Greedily constructing maximal partial \(f\)-factors
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Local Structure When All Maximal Independent Sets Have Equal Weight
• Matching theory
• Maximum induced matchings for chordal graphs in linear time
• Minimal triangulations of graphs: a survey
• Modeling \(k\)-coteries by well-covered graphs
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings
• New results on maximum induced matchings in bipartite graphs and beyond
• On Eulerian and Hamiltonian Graphs and Line Graphs
• On distance-3 matchings and induced matchings
• On graphs with polynomially solvable maximum-weight clique problem
• On the Complexity of General Graph Factor Problems
• On the completeness of a generalized matching problem
• On well-covered triangulations. I
• On well-covered triangulations. II.
• On well-covered triangulations. III
• Recognizing Greedy Structures
• Some covering concepts in graphs
• Some results on graphs without long induced paths
• Split Graphs Having Dilworth Number Two
• The complexity of theorem-proving procedures
• The graphs with maximum induced matching and maximum matching the same size
• The induced matching and chain subgraph cover problems for convex bipartite graphs
• The structure of well-covered graphs and the complexity of their recognition problems
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Well irredundant graphs
• Well-covered claw-free graphs

Cited in

(7)

• Maximal matchings in graphs with large neighborhoods of independent vertices
• Well-indumatched Trees and Graphs of Bounded Girth
• Well-indumatched pseudoforests
• Maximum induced matchings in graphs
• A characterization of well-indumatchable graphs having girth greater than seven
• On graphs with induced matching number almost equal to matching number
• Maximum induced matching problem on hhd-free graphs

This page was built for publication: Graphs with maximal induced matchings of the same size

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