Physical Sciences and Mathematics Commons^™

Precise Partitions Of Large Graphs, Pouria Salehi Nowbandegani

Electronic Theses and Dissertations

First by using an easy application of the Regularity Lemma, we extend some known results about cycles of many lengths to include a specified edge on the cycles. The results in this chapter will help us in rest of this thesis. In 2000, Enomoto and Ota posed a conjecture on the existence of path decomposition of graphs with fixed start vertices and fixed lengths. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices. Furthermore, sharp minimum degree and degree sum conditions …