Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647188 | Discrete Mathematics | 2014 | 7 Pages |
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 Î(G)+|E(G)|â¤2nâf(n), where f(n)=o(n), then G is embeddable. Our result is asymptotically best possible, since for the star Sn (which is not embeddable) we have Î(Sn)+|E(Sn)|=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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Andrzej Żak,