Light spanners and sparse pseudo-random graphs

This thesis is divided into three chapters. Chapter 1 is a brief introduction while Chapters 2 and 3 constitute the main parts of the thesis. These two main chapters are essentially independent.; In Chapter 2, we provide an analysis of the algorithm of Althöfer et al., which shows the existence of “light spanners” for apex graphs, circular are graphs, and similar graph families. We also show that the graphs with no fixed K_r minor have “relatively light spanners”, which yields a quasi-polynomial time approximation scheme (QPTAS) for the TSP problem on such graphs.; In Chapter 3, we present some results about quasi-randomness for sparse graph sequences $Gn\infty n=1$, i.e., p = p(G_n) = = o(1). In particular, we develop some hypotheses under which, the number of labeled copies of a fixed triangle-free graph H in G_n is NH,Gn=&vbm0; V&parl0;Gn&parr0;&vbm0;^{V H}p ^EH . In other words, N(H, G_n) is roughly equal to the expected number of copies of H in the random graph $G$(n,p), where n = |V( G_n)|.