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

5 papers · 1 filter

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…