Zobrazeno 1 - 7
of 7
pro vyhledávání: '"Johannes Pardey"'
Autor:
Johannes Pardey, Dieter Rautenbach
Publikováno v:
Discrete Applied Mathematics. 328:108-116
For a fixed positive $\epsilon$, we show the existence of a constant $C_\epsilon$ with the following property: Given a $\pm1$-edge-labeling $c:E(K_n)\to \{ -1,1\}$ of the complete graph $K_n$ with $c(E(K_n))=0$, and a spanning forest $F$ of $K_n$ of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::210f99e3de43e21afe69d2f93c042aa4
https://doi.org/10.1016/j.dam.2022.12.014
https://doi.org/10.1016/j.dam.2022.12.014
Publikováno v:
Discrete Mathematics. 346:113318
Improving a recent result of Fundikwa, Mazorodze, and Mukwembi, we show that $d \leq (2n-3)/5$ for every connected $C_4$-free graph of order $n$, diameter $d$, and edge-connectivity at least $3$, which is best possible up to a small additive constant
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a5ef151317972e5c844531c04ed468a4
https://doi.org/10.1016/j.disc.2023.113318
https://doi.org/10.1016/j.disc.2023.113318
Publikováno v:
The Electronic Journal of Combinatorics. 29
A classical result of Erdős and Gallai determines the maximum size $m(n,\nu)$ of a graph $G$ of order $n$ and matching number $\nu n$. We show that $G$ has factorially many maximum matchings provided that its size is sufficiently close to $m(n,\nu)$
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1aae74881a8d05338d08655e40f7220d
https://doi.org/10.37236/10610
https://doi.org/10.37236/10610
The independence number $\alpha(G)$ and the dissociation number ${\rm diss}(G)$ of a graph $G$ are the largest orders of induced subgraphs of $G$ of maximum degree at most $0$ and at most $1$, respectively. We consider possible improvements of the ob
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5a663fe179d952cbdf8340f7fd66b160
http://arxiv.org/abs/2205.03404
http://arxiv.org/abs/2205.03404
The dissociation number ${\rm diss}(G)$ of a graph $G$ is the maximum order of a set of vertices of $G$ inducing a subgraph that is of maximum degree at most $1$. Computing the dissociation number of a given graph is algorithmically hard even when re
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41ecd14078ccc283ca5daf3f325227b5
http://arxiv.org/abs/2202.09190
http://arxiv.org/abs/2202.09190
Autor:
Johannes Pardey, Dieter Rautenbach
For a graph $G$ and a not necessarily proper $k$-edge coloring $c:E(G)\to \{ 1,\ldots,k\}$, let $m_i(G)$ be the number of edges of $G$ of color $i$, and call $G$ {\it color-balanced} if $m_i(G)=m_j(G)$ for every two colors $i$ and $j$. Several famous
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8daf9b1813e2963620d7b932de05985c
http://arxiv.org/abs/2105.05661
http://arxiv.org/abs/2105.05661
Publikováno v:
Discrete Mathematics
Discrete Mathematics, Elsevier, 2021, 344 (8), pp.#112439. ⟨10.1016/j.disc.2021.112439⟩
Discrete Mathematics, Elsevier, 2021, 344 (8), pp.#112439. ⟨10.1016/j.disc.2021.112439⟩
A set S of vertices of a graph G is exponentially independent if, for every vertex u in S, ∑ v ∈ S ∖ { u } ( 1 2 ) dist ( G , S ) ( u , v ) − 1 1 , where dist ( G , S ) ( u , v ) is the distance between u and v in the graph G − ( S ∖ { u
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7acee3d81795b465872fb9ee4b6c29ef
https://doi.org/10.1016/j.disc.2021.112439
https://doi.org/10.1016/j.disc.2021.112439