Dieter Rautenbach

activity

20232026

most citedRevisiting Extremal Graphs Having No Stable Cutsets

1 citations · 1 across the 15 of their papers we have counts for

collaborators

Showing math.COShow all

10 papers · 1 filter

math.CO2026

Cyclic Neighborhoods in Digraphs

Thilo Hartel, Dieter Rautenbach

Let $D$ be a digraph of order $n$ and size $m$ with the property that no out-neighborhood or in-neighborhood of any vertex is acyclic. We show that, if $D$ is strongly connected, t…

math.CO2026

Degenerate Vertex Cuts in Sparse Graphs

Thilo Hartel, Johannes Rauch, Dieter Rautenbach

For a non-negative integer $k$ , a vertex cut in a graph is $k$ -degenerate if it induces a $k$ -degenerate subgraph. We show that a graph of order $n$ at least $2 k + 2$ without a $k$ -d…

math.CO2025

On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_{4}$ -free graphs

Thilo Hartel, Lucas Picasarri-Arrieta, Dieter Rautenbach

Let $G$ be a $K_{4}$ -free graph of order $n$ and let $k$ be an integer with $0 \leq k \leq n$ . We show the existence of positive constants $η$ and $ν$ such that $G$ has at most $(4-η)^…

math.CO2025

Majority additive coloring and the maximum degree

Christoph Brause, Dieter Rautenbach, Laurin Schwartze

Kamyczura introduced the notion of a majority additive $k$ -coloring of a graph $G$ as a function $c : V (G) \to {1, 2, \dots, k}$ such that $$\left|\left\{u \in N_G(v):\sum_{w \in N_…

math.CO2025

Leaf to leaf path lengths in trees of given degree sequence

Dieter Rautenbach, Johannes Scherer, Florian Werner

For a tree $T$ , let $l p (T)$ be the number of different lengths of leaf to leaf paths in $T$ . For a degree sequence $s$ of a tree, let $rad (s)$ be the minimum radius of a tree…

math.CO2025

Coloring by Pushing Vertices

Dieter Rautenbach, Laurin Schwartze, Florian Werner

Let $G$ be a graph of order $n$ , maximum degree at most $Δ$ , and no component of order $2$ . Inspired by the famous 1-2-3-conjecture, Bensmail, Marcille, and Orenga define a proper…

math.CO2024

An Optimization Approach to Degree Deviation and Spectral Radius

Dieter Rautenbach, Florian Werner

For a finite, simple, and undirected graph $G$ with $n$ vertices and average degree $d$ , Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\left|d_G(u)-d\right…

math.CO2024★ 1 cited

Revisiting Extremal Graphs Having No Stable Cutsets

Johannes Rauch, Dieter Rautenbach

Confirming a conjecture posed by Caro, it was shown by Chen and Yu that every graph $G$ with $n$ vertices and at most $2 n - 4$ edges has a stable cutset, which is a stable set of ver…

math.CO2024

Forest Cuts in Sparse Graphs

Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach

We propose the conjecture that every graph $G$ of order $n$ with less than $3 n - 6$ edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts a…

math.CO2024

Degree Deviation and Spectral Radius

Dieter Rautenbach, Florian Werner

For a finite, simple, and undirected graph $G$ with $n$ vertices, $m$ edges, and largest eigenvalue $λ$ , Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\lef…

Cyclic Neighborhoods in Digraphs

Degenerate Vertex Cuts in Sparse Graphs

On the number of maximal independent sets and maximal induced bipartite subgraphs in K4​-free graphs

Majority additive coloring and the maximum degree

Leaf to leaf path lengths in trees of given degree sequence

Coloring by Pushing Vertices

An Optimization Approach to Degree Deviation and Spectral Radius

Revisiting Extremal Graphs Having No Stable Cutsets

Forest Cuts in Sparse Graphs

Degree Deviation and Spectral Radius

On the number of maximal independent sets and maximal induced bipartite subgraphs in $K_{4}$ -free graphs