
doi: 10.7282/t3mc9071
In this thesis we present two results in Extremal Graph Theory. The first result is a new proof of a conjecture of Bollobas on embedding trees of bounded degree. The second result is a new proof of the Posa conjecture.Let G=(W,E) be a graph on n vertices having minimum degree at least n/2 + c log(n), where c is a constant. Bela Bollobas conjectured that every tree on n vertices with bounded degree can be embedded into G. We show that this conjecture is true. In fact we show more, that unless G is very close to either the union of two complete graphs on n/2 vertices, or the complement, then a minimum degree of n/2 is sufficient to embed any tree of bounded degree.The k-th power of C is the graph obtained from C by joining every pair of vertices at a distance at most k in C. In 1962 Posa conjectured that any graph G of order n and minimum degree at least 2n/3 contains the square of a Hamiltonian cycle. The conjecture was proven for n > n_0 by Komlos, Sarkozy and Szemeredi using the Regularity Lemma and Blow-up Lemma. The new proof removes the use of the Regularity Lemma and establishes the Posa conjecture using combinatorial arguments, thus vastly reducing n_0.
Graph theory, Extremal problems (Mathematics), Mathematics
Graph theory, Extremal problems (Mathematics), Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
