Precise Partitions Of Large Graphs

<p>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 are proven for the existance of a Hamiltonian cycle passing through specified vertices with prescribed distances between them in large graphs. Finally, we prove a sharp connectivity and degree sum condition for the existence of a subdivision of a multigraph in which some of the vertices are specified and the distance between each pair of vertices in the subdivision is prescribed (within one).</p>

Name thesis:degree_name

Master of Science in Mathematics (M.S.)

Level thesis:degree_level

Thesis (open access)

Discipline thesis:degree_discipline

Department of Mathematical Sciences

Year dc:date.available

2014

Author dc:creator

• Salehi Nowbandegani, Pouria

Contributors dc:contributor

• Andrew Sills
• Hua Wang

• ETD
• Regularity
• Lemma
• cycles
• specified edge
• Hamiltonian cycle
• Discrete Mathematics and Combinatorics

Repository record dc:identifier

https://digitalcommons.georgiasouthern.edu/etd/1181

OAI identifier oai:identifier

oai:digitalcommons.georgiasouthern.edu:etd-2222