18 citations · 46 across the 68 of their papers we have counts for
15 papers · 1 filter
On some Graphs with a Unique Perfect Matching
S. Chaplick, M. Fürst, F. Maffray +1
We show that deciding whether a given graph of size has a unique perfect matching as well as finding that matching, if it exists, can be done in time if is eithe…
Approximating Connected Safe Sets in Weighted Trees
Stefan Ehard, Dieter Rautenbach
For a graph and a non-negative integral weight function on the vertex set of , a set of vertices of is -safe if for every component of the…
Maximal determinants of combinatorial matrices
Henning Bruhn, Dieter Rautenbach
We prove that whenever contains at most ones. We also prove an upper bound on the determinant of matrices with the -con…
A lower bound on the acyclic matching number of subcubic graphs
M. Fürst, D. Rautenbach
The acyclic matching number of a graph is the largest size of an acyclic matching in , that is, a matching in such that the subgraph of induced by the vertices i…
On some hard and some tractable cases of the maximum acyclic matching problem
M. Fürst, D. Rautenbach
Three well-studied types of subgraph-restricted matchings are induced matchings, uniquely restricted matchings, and acyclic matchings. While it is hard to determine the maximum siz…
On the Kőnig-Egerváry Theorem for -Paths
Stéphane Bessy, Pascal Ochem, Dieter Rautenbach
The famous Kőnig-Egerváry theorem is equivalent to the statement that the matching number equals the vertex cover number for every induced subgraph of some graph if and only if tha…