Szczegóły publikacji
Opis bibliograficzny
On embedding graphs with bounded sum of size and maximum degree / Andrzej ŻAK // Discrete Mathematics ; ISSN 0012-365X. — 2014 — vol. 329, s. 12–18. — Bibliogr. s. 18, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 86778 |
|---|---|
| Data dodania do BaDAP | 2015-01-08 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2014.04.001 |
| Rok publikacji | 2014 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
We say that a graph is embeddable if it is a subgraph of its complement. One of the classic results on graphs embedding says that each graph on n vertices with at most n - 2 edges is embeddable. The bound on the number of edges cannot be increased because, for example, the star on n vertices is not embeddable. The reason of this fact is the existence of a vertex with very high degree. In this paper we prove that by forbidding such vertices, one can significantly increase the bound on the number of edges. Namely, we prove that if Delta(G) + vertical bar E(G)vertical bar <= 2n - f(n), where f (n) = 0(n), then G is embeddable. Our result is asymptotically best possible, since for the star S-n (which is not embeddable) we have Delta(S-n)+ vertical bar E(Sn)vertical bar <= 2n - 2. As a corollary, we obtain that a digraph embedding conjecture by Benhocine and Wojda (1985) is true for digraphs with sufficiently many symmetric arcs. (c) 2014 Elsevier B.V. All rights reserved.
