2023-02-06T11:00:10Zhttps://keep.lib.asu.edu/oai/requestoai:keep.lib.asu.edu:node-1565832021-08-27T02:47:01Zoai_pmh:alloai_pmh:repo_items156583
https://hdl.handle.net/2286/R.I.50112
http://rightsstatements.org/vocab/InC/1.0/
2018
v, 98 pages : illustrations (some color)
Doctoral Dissertation
Academic theses
Text
eng
Yie, Jangwon
Czygrinow, Andrzej
Kierstead, Henry
Colbourn, Charles
Fishel, Susanna
Spielberg, John
Arizona State University
Partial requirement for: Ph.D., Arizona State University, 2018
Includes bibliographical references (pages 96-98)
Field of study: Mathematics
Since the seminal work of Tur ́an, the forbidden subgraph problem has been among the central questions in extremal graph theory. Let ex(n;F) be the smallest number m such that any graph on n vertices with m edges contains F as a subgraph. Then the forbidden subgraph problem asks to find ex(n; F ) for various graphs F . The question can be further generalized by asking for the extreme values of other graph parameters like minimum degree, maximum degree, or connectivity. We call this type of question a Tura ́n-type problem. In this thesis, we will study Tura ́n-type problems and their variants for graphs and hypergraphs.<br/><br/>Chapter 2 contains a Tura ́n-type problem for cycles in dense graphs. The main result in this chapter gives a tight bound for the minimum degree of a graph which guarantees existence of disjoint cycles in the case of dense graphs. This, in particular, answers in the affirmative a question of Faudree, Gould, Jacobson and Magnant in the case of dense graphs.<br/><br/>In Chapter 3, similar problems for trees are investigated. Recently, Faudree, Gould, Jacobson and West studied the minimum degree conditions for the existence of certain spanning caterpillars. They proved certain bounds that guarantee existence of spanning caterpillars. The main result in Chapter 3 significantly improves their result and answers one of their questions by proving a tight minimum degree bound for the existence of such structures.<br/><br/>Chapter 4 includes another Tur ́an-type problem for loose paths of length three in a 3-graph. As a corollary, an upper bound for the multi-color Ramsey number for the loose path of length three in a 3-graph is achieved.
Mathematics
Theoretical mathematics
Extremal Graph Theory
Ramsey numbers
Turan Number
Extremal problems (Mathematics)
Graph Theory
Ramsey theory
Some Turán-type problems in extremal graph theory