#### Date

2014

#### Document Type

Dissertation

#### Degree

Doctor of Philosophy

#### Department

Mathematics

#### First Adviser

Isaak, Garth

#### Other advisers/committee members

Magnant, Colton; Stanley, Lee

#### Abstract

In this dissertation we are concerned with sharp degree conditions that guarantee the existence of certain types of subdivisions in large graphs. Of particular interest are subdivisions with a certain number of arbitrarily specified vertices and with prescribed path lengths. Our non-standard approach makes heavy use of the Regularity Lemma (Szemerédi, 1978), the Blow-Up Lemma (Komlós, Sárkózy, and Szemerédi, 1994), and the minimum degree panconnectivity criterion (Williamson, 1977).Sharp minimum degree criteria for a graph G to be H-linked have recently been discovered. We define (H,w,d)-linkage, a condition stronger than H-linkage, by including a weighting function w consisting of required lengths for each edge-path of a desired H-subdivision. We establish sharp minimum degree criteria for a large graph G to be (H,w,d)-linked for all nonnegative d. We similarly define the weaker condition (H,S,w,d)-semi-linkage, where S denotes the set of vertices of H whose corresponding vertices in an H-subdivision are arbitrarily specified. We prove similar sharp minimum degree criteria for a large graph G to be (H,S,w,d)-semi-linked for all nonnegativeWe also examine path coverings in large graphs, which could be seen as a special case of (H,S,w)-semi-linkage. In 2000, Enomoto and Ota conjectured that a graph G of order n with degree sum σ2(G) satisfying σ2(G) > n + k - 2 may be partitioned into k paths, each of prescribed order and with a specified starting vertex. We prove the Enomoto-Ota Conjecture for graphs of sufficiently large order.

#### Recommended Citation

Halperin, Alexander, "Subdivisions with Distance Constraints in Large Graphs" (2014). *Theses and Dissertations*. 1501.

http://preserve.lehigh.edu/etd/1501