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

8 papers · 1 filter

math.CO2021

Diameter, edge-connectivity, and $C_{4}$ -freeness

Vanessa Hiebeler, Johannes Pardey, Dieter Rautenbach

Improving a recent result of Fundikwa, Mazorodze, and Mukwembi, we show that $d \leq (2 n - 3) /5$ for every connected $C_{4}$ -free graph of order $n$ , diameter $d$ , and edge-connectivit…

math.CO2021

Factorially many maximum matchings close to the Erdős-Gallai bound

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta +1

A classical result of Erdős and Gallai determines the maximum size $m (n, ν)$ of a graph $G$ of order $n$ and matching number $ν n$ . We show that $G$ has factorially many maximum matc…

math.CO2021

Unbalanced spanning subgraphs in edge labeled complete graphs

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta +1

Let $K$ be a complete graph of order $n$ . For $d \in (0, 1)$ , let $c$ be a $\pm 1$ -edge labeling of $K$ such that there are $d (2 n)$ edges with label $+ 1$ , and let $G$ be a sp…

math.CO2021

Almost color-balanced perfect matchings in color-balanced complete graphs

Johannes Pardey, Dieter Rautenbach

For a graph $G$ and a not necessarily proper $k$ -edge coloring $c : E (G) \to {1, \dots, k}$ , let $m_{i} (G)$ be the number of edges of $G$ of color $i$ , and call $G$ {\it color-balance…

cs.DS2021

FPT algorithms for packing $k$ -safe spanning rooted sub(di)graphs

Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia +2

We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput. Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] about finding disjoint "balanced…

math.CO2021

Maximally distance-unbalanced 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:…

Diameter, edge-connectivity, and C4​-freeness

Factorially many maximum matchings close to the Erdős-Gallai bound

Unbalanced spanning subgraphs in edge labeled complete graphs

Almost color-balanced perfect matchings in color-balanced complete graphs

FPT algorithms for packing k-safe spanning rooted sub(di)graphs

Maximally distance-unbalanced trees

Diameter, edge-connectivity, and $C_{4}$ -freeness

FPT algorithms for packing $k$ -safe spanning rooted sub(di)graphs