Universität Ulm

output

19942026

most citedArea laws for the entanglement entropy - a review

2.9k citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing math.COShow all

59 papers · 1 filter

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.CO2022★ 8 cited

The classification of preordered spaces in terms of monotones: complexity and optimization

Pedro Hack, Daniel A. Braun, Sebastian Gottwald

The study of complexity and optimization in decision theory involves both partial and complete characterizations of preferences over decision spaces in terms of real-valued monoton…

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…

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

On the edge-Erdős-Pósa property of Ladders

Raphael Steck, Arthur Ulmer

We prove that the ladder with $3$ ~rungs and the house graph have the edge-Erdős-Pósa property, while ladders with $14$ ~rungs or more have not. Additionally, we prove that the latte…

math.CO2019★ 2 cited

Erdős-Pósa from ball packing

Wouter Cames van Batenburg, Gwenaël Joret, Arthur Ulmer

A classic theorem of Erdős and Pósa (1965) states that every graph has either $k$ vertex-disjoint cycles or a set of $O (k lo g k)$ vertices meeting all its cycles. While the standa…

math.CO2019

Even $A$ -cycles have the edge-Erdős-Pósa property

Henning Bruhn

I prove that even $A$ -cycles have the edge-Erdős-Pósa property.

math.CO2019★ 22 cited

Pseudorandom hypergraph matchings

Stefan Ehard, Stefan Glock, Felix Joos

A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect ma…

math.CO2019★ 1 cited

Long $A$ - $B$ -paths have the edge-Erd\H os-Pósa property

Matthias Heinlein, Arthur Ulmer

For a fixed integer $ℓ$ a path is long if its length is at least $ℓ$ . We prove that for all integers $k$ and $ℓ$ there is a number $f (k, ℓ)$ such that for every graph $G…

math.CO2018

On the hardness of deciding the equality of the induced and the uniquely restricted matching number

Maximilian Fürst

If $G (M)$ denotes the subgraph of a graph $G$ induced by the set of vertices that are covered by some matching $M$ in $G$ , then $M$ is an induced or a uniquely restricted matching…

math.CO2018

Algorithmic aspects of broadcast independence

Stéphane Bessy, Dieter Rautenbach

An independent broadcast on a connected graph $G$ is a function $f : V (G) \to N_{0}$ such that, for every vertex $x$ of $G$ , the value $f (x)$ is at most the eccentricity of $x$ …

math.CO2018

The matching number of tree and bipartite degree sequences

F. Bock, D. Rautenbach

We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree de…

math.CO2018★ 1 cited

On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs

M. Fürst, D. Rautenbach

For a matching $M$ in a graph $G$ , let $G (M)$ be the subgraph of $G$ induced by the vertices of $G$ that are incident with an edge in $M$ . The matching $M$ is induced, if $G (M)$ is…

math.CO2018

On the maximum number of maximum independent sets in connected graphs

E. Mohr, D. Rautenbach

We characterize the connected graphs of given order $n$ and given independence number $α$ that maximize the number of maximum independent sets. For $3 \leq α \leq n /2$ , there is a un…

math.CO2018★ 1 cited

Packing A-Paths of Length Zero Modulo Four

Henning Bruhn, Arthur Ulmer

We show that A-paths of length 0 modulo 4 have the Erdős-Pósa property. We also prove that A-paths of length 2 modulo 4 have the property but that A-paths of length 1 or of length…

math.CO2018

On the maximum number of minimum dominating sets in forests

J. D. Alvarado, S. Dantas, E. Mohr +1

Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number $γ$ has at most $2^{γ}$ minimum dominating sets. Bien gave a counterexample, which allows t…

math.CO2018★ 3 cited

On the maximum number of minimum total dominating sets in forests

Michael A. Henning, Elena Mohr, Dieter Rautenbach

We propose the conjecture that every tree with order $n$ at least $2$ and total domination number $γ_{t}$ has at most $\left(\frac{n-\frac{γ_t}{2}}{\frac{γ_t}{2}}\right)^{\frac{γ_t}{…

math.CO2017

On some Graphs with a Unique Perfect Matching

S. Chaplick, M. Fürst, F. Maffray +1

We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O (m)$ if $G$ is eithe…

math.CO2017★ 2 cited

A lower bound on the acyclic matching number of subcubic graphs

M. Fürst, D. Rautenbach

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$ , that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices i…

math.CO2017★ 3 cited

On some hard and some tractable cases of the maximum acyclic matching problem

M. Fürst, D. Rautenbach

Three well-studied types of subgraph-restricted matchings are induced matchings, uniquely restricted matchings, and acyclic matchings. While it is hard to determine the maximum siz…

math.CO2017

On the Kőnig-Egerváry Theorem for $k$ -Paths

Stéphane Bessy, Pascal Ochem, Dieter Rautenbach

The famous Kőnig-Egerváry theorem is equivalent to the statement that the matching number equals the vertex cover number for every induced subgraph of some graph if and only if tha…

math.CO2017

Locally Searching for Large Induced Matchings

Maximilian Fürst, Marilena Leichter, Dieter Rautenbach

It is an easy observation that a natural greedy approach yields a $(d - O (1))$ -factor approximation algorithm for the maximum induced matching problem in $d$ -regular graph…

math.CO2017

Sandwiches Missing Two Ingredients of Order Four

José D. Alvarado, Simone Dantas, Dieter Rautenbach

For a set $F$ of graphs, an instance of the $F$ -{\sc free Sandwich Problem} is a pair $(G_{1}, G_{2})$ consisting of two graphs $G_{1}$ and $G_{2}$ with the same vertex set su…

math.CO2017★ 1 cited

Degenerate Matchings and Edge Colorings

Julien Baste, Dieter Rautenbach

A matching $M$ in a graph $G$ is $r$ -degenerate if the subgraph of $G$ induced by the set of vertices incident with an edge in $M$ is $r$ -degenerate. Goddard, Hedetniemi, Hedetniem…

Forest Cuts in Sparse Graphs

The classification of preordered spaces in terms of monotones: complexity and optimization

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

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

On the edge-Erdős-Pósa property of Ladders

Erdős-Pósa from ball packing

Even A-cycles have the edge-Erdős-Pósa property

Pseudorandom hypergraph matchings

Long A-B-paths have the edge-Erd\H os-Pósa property

On the hardness of deciding the equality of the induced and the uniquely restricted matching number

Algorithmic aspects of broadcast independence

The matching number of tree and bipartite degree sequences

On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs

On the maximum number of maximum independent sets in connected graphs

Packing A-Paths of Length Zero Modulo Four

On the maximum number of minimum dominating sets in forests

On the maximum number of minimum total dominating sets in forests

On some Graphs with a Unique Perfect Matching

A lower bound on the acyclic matching number of subcubic graphs

On some hard and some tractable cases of the maximum acyclic matching problem

On the Kőnig-Egerváry Theorem for k-Paths

Locally Searching for Large Induced Matchings

Sandwiches Missing Two Ingredients of Order Four

Degenerate Matchings and Edge Colorings

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

Even $A$ -cycles have the edge-Erdős-Pósa property

Long $A$ - $B$ -paths have the edge-Erd\H os-Pósa property

On the Kőnig-Egerváry Theorem for $k$ -Paths