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 2020Show all

8 papers · 1 filter

math.CO2020

Minimum distance-unbalancedness of trees

Marie Kramer, Dieter Rautenbach

For a graph $G$ , and two distinct vertices $u$ and $v$ of $G$ , let $n_{G} (u, v)$ be the number of vertices of $G$ that are closer in $G$ to $u$ than to $v$ . Miklavič and Šparl (arXiv:…

math.CO2020

Low Weight Perfect Matchings

Stefan Ehard, Elena Mohr, Dieter Rautenbach

Answering a question posed by Caro, Hansberg, Lauri, and Zarb, we show that for every positive integer $n$ and every function $σ : E (K_{4 n}) \to {- 1, 1}$ with $σ\left(E(K_{4n})\…

math.CO2020

Exponential Independence in Subcubic Graphs

Stéphane Bessy, Johannes Pardey, Dieter Rautenbach

A set $S$ of vertices of a graph $G$ is exponentially independent if, for every vertex $u$ in $S$ , $$\sum\limits_{v\in S\setminus \{ u\}}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)…

math.CO2020★ 1 cited

Non-monotone target sets for threshold values restricted to $0$ , $1$ , and the vertex degree

Julien Baste, Stefan Ehard, Dieter Rautenbach

We consider a non-monotone activation process $(X_{t})_{t \in {0, 1, 2, \dots}}$ on a graph $G$ , where $X_{0} \subseteq V (G)$ , $X_{t} = {u \in V (G) : ∣ N_{G} (u) \cap X_{t - 1} ∣ \geq τ (u)}$ for ever…

math.CO2020

Reconfiguring dominating sets in minor-closed graph classes

Dieter Rautenbach, Johannes Redl

For a graph $G$ , two dominating sets $D$ and $D^{'}$ in $G$ , and a non-negative integer $k$ , the set $D$ is said to $k$ -transform to $D^{'}$ if there is a sequence $D_{0}, \dots, D_{ℓ}$ of…

math.CO2020

Biholes in balanced bipartite graphs

Stefan Ehard, Elena Mohr, Dieter Rautenbach

A bihole in a bipartite graph $G$ with partite sets $A$ and $B$ is an independent set $I$ in $G$ with $∣ I \cap A ∣ = ∣ I \cap B ∣$ . We prove lower bounds on the largest order of biholes i…

Minimum distance-unbalancedness of trees

Low Weight Perfect Matchings

Exponential Independence in Subcubic Graphs

Non-monotone target sets for threshold values restricted to 0, 1, and the vertex degree

Reconfiguring dominating sets in minor-closed graph classes

Biholes in balanced bipartite graphs

Non-monotone target sets for threshold values restricted to $0$ , $1$ , and the vertex degree