Szczegóły publikacji
Opis bibliograficzny
On packing two graphs with bounded sum of sizes and maximum degree / Andrzej ŻAK // SIAM Journal on Discrete Mathematics ; ISSN 0895-4801. — 2014 — vol. 28 no. 4, s. 1686–1698. — Bibliogr. s. 1698, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 86780 |
|---|---|
| Data dodania do BaDAP | 2015-01-08 |
| Tekst źródłowy | URL |
| DOI | 10.1137/130940499 |
| Rok publikacji | 2014 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | SIAM Journal on Discrete Mathematics |
Abstract
A packing of graphs G(1) and G(2), both on n vertices, is a set {H-1, H-2} such that H-1 congruent to G(1), H-2 congruent to G(2), and H-1 and H-2 are edge disjoint subgraphs of K-n. In 1978, Sauer and Spencer [J. Combin. Theory Ser. B, 25 (1978), pp. 295 302] proved that if | E(G(1))| | |E(G(2))| < (3)(2)n-1, then there is a packing of G(1) and G(2). Independently, Bollobas and Eldridge [J. Combin. Theory Ser. B, 25 (1978), pp. 105-124] obtained a stronger result. Namely, they proved that if | E(G(1))|+| E(G(2))| <= 2n-4, then there is a packing of G(1) and G(2), provided that Delta(G(1)) < n- 1 and Delta(G(2)) < n- 1. In this paper we prove that for sufficiently large n, if |E(G(1))| + |E(G(2))|+ max{Delta(G(1)),Delta(G(2))} < 5/2n - 2, then there is a packing of G(1) and G(2). The bound is tight. Furthermore, we prove that if |E(G(1))| + |E(G(2))|+ max{Delta(G(1)),Delta(G(2))} <= 3n - alpha(n), where alpha(n) = o(n), then there is a packing of G(1) and G(2), provided that Delta(G(1)) < n-1 and Delta(G(2)) < n-1. The bound is asymptotically tight.
