On two extensions of equimatchable graphs

DOI10.1016/j.disopt.2017.08.002zbMath1387.05194arXiv1612.08531OpenAlexW2754758920MaRDI QIDQ1751251

Mordechai Shalom, Martin Milanič, Tatiana Romina Hartinger, Zakir Deniz, Tınaz Ekim

Publication date: 24 May 2018

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

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

zbMATH Keywords

parameterized complexityedge dominating setGallai-Edmonds decompositionequimatchable graphminimum maximal matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph designs and isomorphic decomposition (05C51)

Related Items (3)

Well-indumatched Trees and Graphs of Bounded Girth ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Equimatchable bipartite graphs

Cites Work

• Fundamentals of parameterized complexity
• On minimum maximal distance-\(k\) matchings
• On three extensions of equimatchable graphs
• Bounding the size of equimatchable graphs of fixed genus
• Matching theory
• Matching-perfect and cover-perfect graphs
• The structure of well-covered graphs and the complexity of their recognition problems
• Some APX-completeness results for cubic graphs
• Minimal graphs for matching extensions
• On two equimatchable graph classes
• Efficient recognition of equimatchable graphs
• TWO THEOREMS IN GRAPH THEORY
• Equimatchable Graphs on Surfaces
• Edge Dominating Sets in Graphs
• Matchings in polytopal graphs
• Equimatchable factor‐critical graphs
• Parameterized Algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On two extensions of equimatchable graphs