Zobrazeno 1 - 10
of 826
pro vyhledávání: '"Rautenbach Dieter"'
Autor:
Mohr Elena, Rautenbach Dieter
Publikováno v:
Discussiones Mathematicae Graph Theory, Vol 42, Iss 1, Pp 309-313 (2022)
We show that every claw-free cubic graph of order n at least 8 has at most 2⌊n4⌋{2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs.
Externí odkaz:
https://doaj.org/article/373a713b522f4c52bc1f11bd75b29ccc
We propose the conjecture that every graph $G$ of order $n$ with less than $3n-6$ edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts and show that the density condition would be best possible. We verify t
Externí odkaz:
http://arxiv.org/abs/2409.17724
Autor:
Rautenbach, Dieter, Werner, Florian
For a finite, simple, and undirected graph $G$ with $n$ vertices, $m$ edges, and largest eigenvalue $\lambda$, Nikiforov introduced the degree deviation of $G$ as $s=\sum_{u\in V(G)}\left|d_G(u)-\frac{2m}{n}\right|$. Contributing to a conjecture of N
Externí odkaz:
http://arxiv.org/abs/2409.14956
Autor:
Gomes, Guilherme C. M., Masquio, Bruno P., Pinto, Paulo E. D., Rautenbach, Dieter, Santos, Vinicius F. dos, Szwarcfiter, Jayme L., Werner, Florian
A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and induced matching numbers are defined as the maximum cardinality of suc
Externí odkaz:
http://arxiv.org/abs/2409.04855
Publikováno v:
Discussiones Mathematicae Graph Theory, Vol 40, Iss 3, Pp 841-853 (2020)
For an integer k at least 2, and a graph G, let fk(G) be the minimum cardinality of a set X of vertices of G such that G − X has either k vertices of maximum degree or order less than k. Caro and Yuster [Discrete Mathematics 310 (2010) 742–747] c
Externí odkaz:
https://doaj.org/article/3e2d65522ec74332bf2fa31e4d2bd7db
Autor:
Fürst Maximilian, Rautenbach Dieter
Publikováno v:
Discussiones Mathematicae Graph Theory, Vol 40, Iss 1, Pp 355-360 (2020)
We provide a short proof of a conjecture of Davila and Kenter concerning a lower bound on the zero forcing number Z(G) of a graph G. More specifically, we show that Z(G) ≥ (g − 2)(δ − 2) + 2 for every graph G of girth g at least 3 and minimum
Externí odkaz:
https://doaj.org/article/87b1b4a9dfda4032a4a7e12c2bb48735
Publikováno v:
Discussiones Mathematicae Graph Theory, Vol 38, Iss 1, Pp 275-285 (2018)
We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G.
Externí odkaz:
https://doaj.org/article/a578aa7f00cb43f3be47d8780a861f37
Autor:
Rautenbach, Dieter, Werner, Florian
Graph isomorphism, subgraph isomorphism, and maximum common subgraphs are classical well-investigated objects. Their (parameterized) complexity and efficiently tractable cases have been studied. In the present paper, for a given set of forests, we st
Externí odkaz:
http://arxiv.org/abs/2403.14492
Autor:
Rautenbach, Dieter, Werner, Florian
A common subgraph of two graphs $G_1$ and $G_2$ is a graph that is isomorphic to subgraphs of $G_1$ and $G_2$. In the largest common subgraph problem the task is to determine a common subgraph for two given graphs $G_1$ and $G_2$ that is of maximum p
Externí odkaz:
http://arxiv.org/abs/2403.03696
Publikováno v:
Discussiones Mathematicae Graph Theory, Vol 37, Iss 4, Pp 953-961 (2017)
For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman do
Externí odkaz:
https://doaj.org/article/92032396bfb54de585fca8475eee98d4