D. Rautenbach

activity

20092023

most citedHow to determine if a random graph with a fixed degree sequence has a giant component

18 citations · 46 across the 68 of their papers we have counts for

collaborators

Showing 2017 · math.COShow all

13 papers · 2 filters

math.CO2017

On some Graphs with a Unique Perfect Matching

S. Chaplick, M. Fürst, F. Maffray +1

We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O (m)$ if $G$ is eithe…

math.CO2017

Approximating Connected Safe Sets in Weighted Trees

Stefan Ehard, Dieter Rautenbach

For a graph $G$ and a non-negative integral weight function $w$ on the vertex set of $G$ , a set $S$ of vertices of $G$ is $w$ -safe if $w (C) \geq w (D)$ for every component $C$ of the…

math.CO2017

Maximal determinants of combinatorial matrices

Henning Bruhn, Dieter Rautenbach

We prove that $det A \leq 6^{\frac{n}{6}}$ whenever $A \in {0, 1}^{n \times n}$ contains at most $2 n$ ones. We also prove an upper bound on the determinant of matrices with the $k$ -con…

math.CO2017★ 2 cited

A lower bound on the acyclic matching number of subcubic graphs

M. Fürst, D. Rautenbach

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$ , that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices i…

math.CO2017★ 3 cited

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…

math.CO2017

On the Kőnig-Egerváry Theorem for $k$ -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…

math.CO2017

Locally Searching for Large Induced Matchings

Maximilian Fürst, Marilena Leichter, Dieter Rautenbach

It is an easy observation that a natural greedy approach yields a $(d - O (1))$ -factor approximation algorithm for the maximum induced matching problem in $d$ -regular graph…

math.CO2017

The Cat and the Noisy Mouse

Dieter Rautenbach, Moritz Schneider

We consider a variant of a pursuit and evasion game studied independently by Britnell and Wildon as well as Haslegrave. In their game, a cat has to catch an invisible mouse that mo…

math.CO2017★ 1 cited

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 $Z (G)$ of a graph $G$ . More specifically, we show that $Z(G)\geq (…

math.CO2017

Equating $k$ Maximum Degrees in Graphs without Short Cycles

M. Fürst, M. Gentner, M. A. Henning +2

For an integer $k$ at least $2$ , and a graph $G$ , let $f_{k} (G)$ be the minimum cardinality of a set $X$ of vertices of $G$ such that $G - X$ has either $k$ vertices of maximum degree…

math.CO2017

Sandwiches Missing Two Ingredients of Order Four

José D. Alvarado, Simone Dantas, Dieter Rautenbach

For a set $F$ of graphs, an instance of the $F$ -{\sc free Sandwich Problem} is a pair $(G_{1}, G_{2})$ consisting of two graphs $G_{1}$ and $G_{2}$ with the same vertex set su…

math.CO2017

Constant Threshold Intersection Graphs of Orthodox Paths in Trees

Claudson Ferreira Bornstein, José Wilson Coura Pinto, Dieter Rautenbach +1

A graph $G$ belongs to the class $ORTH [h, s, t]$ for integers $h$ , $s$ , and $t$ if there is a pair $(T, S)$ , where $T$ is a tree of maximum degree at most $h$ , and ${\cal…

math.CO2017★ 1 cited

Degenerate Matchings and Edge Colorings

Julien Baste, Dieter Rautenbach

A matching $M$ in a graph $G$ is $r$ -degenerate if the subgraph of $G$ induced by the set of vertices incident with an edge in $M$ is $r$ -degenerate. Goddard, Hedetniemi, Hedetniem…

On some Graphs with a Unique Perfect Matching

Approximating Connected Safe Sets in Weighted Trees

Maximal determinants of combinatorial matrices

A lower bound on the acyclic matching number of subcubic graphs

On some hard and some tractable cases of the maximum acyclic matching problem

On the Kőnig-Egerváry Theorem for k-Paths

Locally Searching for Large Induced Matchings

The Cat and the Noisy Mouse

A Short Proof for a Lower Bound on the Zero Forcing Number

Equating k Maximum Degrees in Graphs without Short Cycles

Sandwiches Missing Two Ingredients of Order Four

Constant Threshold Intersection Graphs of Orthodox Paths in Trees

Degenerate Matchings and Edge Colorings

On the Kőnig-Egerváry Theorem for $k$ -Paths

Equating $k$ Maximum Degrees in Graphs without Short Cycles