Masters Theses
Permanent URI for this collection
Browse
Browsing Masters Theses by Subject "4connected"
Results Per Page
Sort Options

ItemNonSeparating Cycles Through Prescirbed Vertices in Plane Graphs(Middle Tennessee State University, 2024) Moser, Jacob ; Ye, Dong ; Stephens, Chris ; Zha, XiaoyaA graph G is kconnected if it has at least k + 1 vertices and remains connected after deleting k − 1 vertices of G. A plane graph is a graph G with an embedding on a plane R2 such that the interior of an edge contains no vertex and no point of any other edge. When G is a plane graph, we call the regions of R2\G the faces of G. A planar graph is a graph isomorphic to a plane graph. A plane triangulation is a plane graph in which each face is bounded by a 3cycle. A graph G is klinked if, for any given 2k vertices there are k disjoint paths joining each pair of them. For a given graph H, a graph G is Hlinked if, for every injective map from the vertices of H to the vertices of G, G contains a subdivision of H. Let (K4 − e) be the graph obtained from K4 by removing one edge. A graph G is (K4 − e)linked if, for every injective map from the vertices of K4 − e to the vertices of G, G contains a subdivision of K4 − e. A graph is said to be kcyclable if given any set of k vertices there is a cycle that contains the k vertices. We say that a graph is kordered or Cklinked if given any set of k vertices there is a cycle through the k vertices in any specified order. A graph is (K2 ∪ K3)linked if for every set of two vertices and every set of three vertices there exists a path joining the two vertices and a cycle on the three vertices. Seymour and Thomassen’s 2linkage theorem characterizes all graphs which have two disjoint paths connecting any given two pair of vertices. Goddard proved that every 4connected maximal planar graph is 4ordered. Ellingham, Plummer, and Yu proved that any 4connected planar triangulation is (K4 − e)linked. In this thesis we completely characterize the obstructions to (K2 ∪ K3)linkage in 4connected plane triangulations. From these obstructions we can see that no 4connected nor 5connected plane triangulation is (K2 ∪ K3)linked. iii