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

102 papers

cs.DS2023

Exact and Parameterized Algorithms for the Independent Cutset Problem

Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza

The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is $NP$ -complete even when th…

math.CO2023

Mostar index and bounded maximum degree

Michael A. Henning, Johannes Pardey, Dieter Rautenbach +1

Došlić et al. defined the Mostar index of a graph $G$ as $M o (G) = uv \in E (G) \sum ∣ n_{G} (u, v) - n_{G} (v, u) ∣$ , where, for an edge $uv$ of $G$ , the term $n_{G} (u, v)$ denotes the number…

math.CO2023

Sparse vertex cutsets and the maximum degree

Stéphane Bessy, Johannes Rauch, Dieter Rautenbach +1

We show that every graph $G$ of maximum degree $Δ$ and sufficiently large order has a vertex cutset $S$ of order at most $Δ$ that induces a subgraph $G [S]$ of maximum degree at mos…

math.CO2023

Irregularity of Graphs respecting Degree Bounds

Dieter Rautenbach, Florian Werner

Albertson defined the irregularity of a graph $G$ as $i r r (G) = uv \in E (G) \sum ∣ d_{G} (u) - d_{G} (v) ∣$ . For a graph $G$ with $n$ vertices, $m$ edges, maximum degree $Δ$ , and $d=\lef…

math.CO2023

Vertex degrees close to the average degree

Johannes Pardey, Dieter Rautenbach

Let $G$ be a finite, simple, and undirected graph of order $n$ and average degree $d$ . Up to terms of smaller order, we characterize the minimal intervals $I$ containing $d$ that a…

math.CO2022★ 1 cited

Bounding the Mostar index

Štefko Miklavič, Johannes Pardey, Dieter Rautenbach +1