3 citations · 7 across the 7 of their papers we have counts for
11 papers
Acyclic matchings in graphs of bounded maximum degree
Julien Baste, Maximilian Fürst, Dieter Rautenbach
A matching in a graph is acyclic if the subgraph of induced by the set of vertices that are incident to an edge in is a forest. We prove that every graph with v…
Domination versus edge domination
Julien Baste, Maximilian Fürst, Michael A. Henning +2
We propose the conjecture that the domination number of a -regular graph with is always at most its edge domination number , which coincides with th…
Bounding and approximating minimum maximal matchings in regular graphs
Julien Baste, Maximilian Fürst, Michael A. Henning +2
The edge domination number of a graph is the minimum size of a maximal matching in . It is well known that this parameter is computationally very hard, and several…
Linear programming based approximation for unweighted induced matchings --- breaking the barrier
Julien Baste, Maximilian Fürst, Dieter Rautenbach
A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induc…
Uniquely restricted matchings in subcubic graphs without short cycles
Maximilian Fürst, Dieter Rautenbach
A matching in a graph is uniquely restricted if no other matching in covers the same set of vertices. We prove that any connected subcubic graph with vertices and g…
On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
M. Fürst, D. Rautenbach
For a matching in a graph , let be the subgraph of induced by the vertices of that are incident with an edge in . The matching is induced, if is…
Uniquely restricted matchings in subcubic graphs
Maximilian Fürst, Michael A. Henning, Dieter Rautenbach
A matching in a graph is uniquely restricted if no other matching in covers the same set of vertices. We conjecture that every connected subcubic graph with edges a…
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…
A Short Proof for a Lower Bound on the Zero Forcing Number
M. Fürst, D. Rautenbach
We provide a short proof of a conjecture of Davila and Kenter concerning a lower bound on the zero forcing number of a graph . More specifically, we show that $Z(G)\geq (…
Equating Maximum Degrees in Graphs without Short Cycles
M. Fürst, M. Gentner, M. A. Henning +2
For an integer at least , and a graph , let be the minimum cardinality of a set of vertices of such that has either vertices of maximum degree…