Szczegóły publikacji
Opis bibliograficzny
A note on packing two copies of a tree into a graph with small maximum degree / Agnieszka GÖRLICH, Mariusz WOŹNIAK // Discrete Mathematics ; ISSN 0012-365X. — 2020 — vol. 343 art. no. 111991, s. 1–6. — Bibliogr. s. 6, Abstr.
Autorzy (2)
Dane bibliometryczne
ID BaDAP | 128964 |
---|---|
Data dodania do BaDAP | 2020-06-16 |
Tekst źródłowy | URL |
DOI | 10.1016/j.disc.2020.111991 |
Rok publikacji | 2020 |
Typ publikacji | artykuł w czasopiśmie |
Otwarty dostęp | |
Czasopismo/seria | Discrete Mathematics |
Abstract
Let T be a non-star tree of order n and maximum degree Δ. Hong Wang showed that there is a packing σ such that the degree of every vertex v in T⊕σ(T) does not exceed Δ(T)+2. In this note we improve this result in two directions. First, we show that with only one exception, there exists a packing σ such that Δ(T⊕σ(T))≤Δ(T)+1. Moreover, this bound is, in a sense, uniform. © 2020 Elsevier B.V.