On some graphs with a unique perfect matching

DOI10.1016/j.ipl.2018.07.008zbMath1481.05125arXiv1712.04228OpenAlexW2962901871MaRDI QIDQ1799576

Steven Chaplick, Dieter Rautenbach, Frédéric Maffray, Maximilian Fürst

Publication date: 19 October 2018

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

split graphclaw-free graphgraph algorithmsunique perfect matchingcograph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Distance spectrum, 1-factor and vertex-disjoint cycles ⋮ Some tight bounds on the minimum and maximum forcing numbers of graphs

Cites Work

• Unnamed Item
• Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
• On graphs with a unique perfect matching
• An O(\(n\)) time algorithm for maximum matching on cographs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• Unique Maximum Matching Algorithms
• A Linear Recognition Algorithm for Cographs
• Graphs with 1-Factors
• A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
• Uniquely restricted matchings

This page was built for publication: On some graphs with a unique perfect matching