# Search results for: Dieter Rautenbach

Journal of Graph Theory > 89 > 1 > 55 - 63

*M*in a graph

*G*is uniquely restricted if there is no matching ${M}^{\prime}$ in

*G*that is distinct from

*M*but covers the same vertices as

*M*. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely...

Journal of Graph Theory > 88 > 2 > 356 - 370

*G*of order

*n*at least three, Matheson and Tarjan showed that

*G*has domination number at most $n/3$. Similarly, for a maximal outerplanar graph

*G*of order

*n*at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that

*G*has total domination number at most $2n/5$ unless

*G*is isomorphic to one of two exceptional graphs of order 12. We present...

Journal of Graph Theory > 88 > 1 > 131 - 145

*d*of nonnegative integers, let $G\left(d\right)$ and $F\left(d\right)$ be the sets of all graphs and forests with degree sequence

*d*, respectively. Let ${\gamma}_{min}\left(d\right)=min\{\gamma \left(G\right):G\in G\left(d\right)\}$, ${\alpha}_{max}\left(d\right)=max\{\alpha \left(G\right):G\in G\left(d\right)\}$, ${\gamma}_{min}^{F}\left(d\right)=min\{\gamma \left(F\right):F\in F\left(d\right)\}$, and ${\alpha}_{max}^{F}\left(d\right)=max\{\alpha \left(F\right):F\in F\left(d\right)\}$ where $\gamma \left(G\right)$ is the domination number and $\alpha \left(G\right)$ is the independence number of a graph

*G*. Adapting results of Havel and Hakimi, Rao showed in 1979 that ${\alpha}_{max}$...

Discrete Applied Mathematics > 2018 > 236 > C > 203-213

Discussiones Mathematicae Graph Theory > 2017 > 38 > 1 > 275-285

Discrete Applied Mathematics > 2018 > 235 > C > 16-22

Discrete Mathematics > 2018 > 341 > 1 > 119-125

Theoretical Computer Science > 2017 > 704 > C > 92-93

Discrete Applied Mathematics > 2017 > 232 > C > 73-87

Discussiones Mathematicae Graph Theory > 2017 > 37 > 4 > 953-961

Electronic Notes in Discrete Mathematics > 2017 > 62 > C > 99-104

Electronic Notes in Discrete Mathematics > 2017 > 62 > C > 291-296

Discrete Mathematics > 2017 > 340 > 11 > 2650-2658

Annals of Operations Research > 2018 > 264 > 1-2 > 267-286

Theoretical Computer Science > 2017 > 689 > C > 27-35

Information Processing Letters > 2017 > 124 > C > 26-29

Discrete Mathematics > 2017 > 340 > 7 > 1497-1502

Graphs and Combinatorics > 2017 > 33 > 4 > 789-799

*d*. We show that if $$d_n\ge 1$$ d n ≥ 1 , then $$\chi _{\min }(d)\le \max \left\{ 3,d_1-\frac{n+1}{4d_1}+4\right\}...

Discrete Applied Mathematics > 2017 > 223 > C > 64-71

Discrete Mathematics > 2017 > 340 > 4 > 596-606