Elena Mohr

activity

20182021

most citedOn the maximum number of minimum total dominating sets in forests

3 citations · 3 across the 4 of their papers we have counts for

collaborators

Showing math.COShow all

11 papers · 1 filter

math.CO2021

Zero-sum copies of spanning forests in zero-sum complete graphs

Elena Mohr, Johannes Pardey, Dieter Rautenbach

For a complete graph $K_{n}$ of order $n$ , an edge-labeling $c : E (K_{n}) \to {- 1, 1}$ satisfying $c (E (K_{n})) = 0$ , and a spanning forest $F$ of $K_{n}$ , we consider the problem to minimize…

math.CO2020

Low Weight Perfect Matchings

Stefan Ehard, Elena Mohr, Dieter Rautenbach

Answering a question posed by Caro, Hansberg, Lauri, and Zarb, we show that for every positive integer $n$ and every function $σ : E (K_{4 n}) \to {- 1, 1}$ with $σ\left(E(K_{4n})\…

math.CO2020

Biholes in balanced bipartite graphs

Stefan Ehard, Elena Mohr, Dieter Rautenbach

A bihole in a bipartite graph $G$ with partite sets $A$ and $B$ is an independent set $I$ in $G$ with $∣ I \cap A ∣ = ∣ I \cap B ∣$ . We prove lower bounds on the largest order of biholes i…

math.CO2019

Cubic graphs with equal independence number and matching number

Elena Mohr, Dieter Rautenbach

Caro, Davila, and Pepper (arXiv:1909.09093) recently proved $δ (G) α (G) \leq Δ (G) μ (G)$ for every graph $G$ with minimum degree $δ (G)$ , maximum degree $Δ (G)$ , independence number $α(…

math.CO2019

Domination versus edge domination

Julien Baste, Maximilian Fürst, Michael A. Henning +2

We propose the conjecture that the domination number $γ (G)$ of a $Δ$ -regular graph $G$ with $Δ \geq 1$ is always at most its edge domination number $γ_{e} (G)$ , which coincides with th…

math.CO2019

Bounding and approximating minimum maximal matchings in regular graphs

Julien Baste, Maximilian Fürst, Michael A. Henning +2

The edge domination number $γ_{e} (G)$ of a graph $G$ is the minimum size of a maximal matching in $G$ . It is well known that this parameter is computationally very hard, and several…

math.CO2018

Rainbow triangles and cliques in edge-colored graphs

Stefan Ehard, Elena Mohr

For an edge-colored graph, a subgraph is called rainbow if all its edges have distinct colors. We show that if $G$ is an edge-colored graph of order $n$ and size $m$ using $c$ colo…

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

On the maximum number of maximum independent sets

Elena Mohr, Dieter Rautenbach

We give a very short and simple proof of Zykov's generalization of Turán's theorem, which implies that the number of maximum independent sets of a graph of order $n$ and independen…

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}{…