Text

ETD_2800

http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417

theses

In this thesis we are going to present some results on embedding spanning subgraphs into large dense graphs. Spanning Trees Bollob'as conjectured that if $G$ is a graph on $n$ vertices, $delta(G) geq (1/2 + epsilon) n$ for some $epsilon > 0$, and $T$ is a bounded degree tree on $n$ vertices, then $T$ is a subgraph of $G$. The problem was solved in the affirmative by Koml'os, S'ark"ozy and Szemer'edi for large graphs. They then strengthened their result, and showed that the maximum degree of $T$ need not be bounded: there exists a constant $c$ such that $T$ is a subgraph of $G$ if $Delta(T) leq cn / log n$, $delta(G) geq (1/2 + epsilon) n$ and $n$ is large. Both proofs are based on the Regularity Lemma-Blow-up Lemma Method. Recently, using other methods, it was shown that bounded degree trees embed into graphs with minimum degree $n/2 + C log n$, where $C$ is a constant depending on the maximum degree of $T$. Here we show that in general $n/2 + O(Delta(T) cdot log n)$ is sufficient for every $Delta(T) leq cn / log n$. We also show that this bound is tight for the two extreme values of $m$ i.e. when $m = C$ and when $m = cn / log n$. Powers of Hamiltonian Cycles In 1962 P'osa conjectured that if $delta(G) geq frac{2}{3}n$ then $G$ contains the square of a Hamiltonian cycle. Later, in 1974, Seymour generalized this conjecture: if $delta(G) geq (frac{k-1}{k})n$ then $G$ contains the $(k-1)$th power of a Hamiltonian cycle. In 1998 the conjecture was proved by Koml'os, S'ark"ozy and Szemer'edi for large graphs using the Regularity Lemma. We present a ``deregularised" proof of the P'osa-Seymour conjecture which results in a much lower threshold value for $n$, the size of the graph for which the conjecture is true. We hope that the tools used in this proof will push down the threshold value for $n$ to around 100 at which point we will be able to verify the conjecture for every $n$.

Ph.D.

Includes bibliographical references

Includes vita

by Asif Jamshed

doi:10.7282/T3MC8ZSD

ETD doctoral

The author owns the copyright to this work.

ETD

application/pdf

application/x-tar

573440

3851733be0841462f50e102097a59eeb5adda2d3