{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/105617"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/105617","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Sufficient degree conditions for graph embeddings","abstract":"In this dissertation, we focus on the sufficient conditions to guarantee one graph being the subgraph of another. In Chapter 2, we discuss list packing, a modification of the idea of graph packing. This is fitting one graph in the complement of another graph. Sauer and Spencer showed a sufficient bound involving maximum degrees, and this was further explored by Kaul and Kostochka to characterize all extremal cases. Bollobas and Eldridge (and independently Sauer and Spencer) developed edge sum bounds to guarantee packing. In Chapter 2, we introduce the new idea of list packing and use it to prove stronger versions of many existing theorems. Namely, for two graphs, if the product of the maximum degrees is small or if the total number of edges is small, then the graphs pack. In Chapter 3, we discuss the problem of finding k vertex-disjoint cycles in a multigraph. This problem originated from a conjecture of Erdos and has led to many different results. Corradi and Hajnal looked at a minimum degree condition. Enomoto and Wang independently looked at a minimum degree-sum condition. More recently, Kierstead, Kostochka, and Yeager characterized the extremal cases to improve these bounds. In Chapter 3, we improve on the multigraph degree-sum result. We characterize all multigraphs that have simple Ore-degree at least 4k -3 , but do not contain k vertex-disjoint cycles. Moreover, we provide a polynomial time algorithm for deciding if a graph contains k vertex-disjoint cycles. Lastly, in Chapter 4, we consider the same problem but with chorded cycles. Finkel looked at the minimum degree condition while Chiba, Fujita, Gao, and Li addressed the degree-sum condition. More recently, Molla, Santana, and Yeager improved this degree-sum result, and in Chapter 4, we will improve on this further.","abstract_html":"In this dissertation, we focus on the sufficient conditions to guarantee one graph being the subgraph of another. In Chapter 2, we discuss list packing, a modification of the idea of graph packing. This is fitting one graph in the complement of another graph. Sauer and Spencer showed a sufficient bound involving maximum degrees, and this was further explored by Kaul and Kostochka to characterize all extremal cases. Bollobas and Eldridge (and independently Sauer and Spencer) developed edge sum bounds to guarantee packing. In Chapter 2, we introduce the new idea of list packing and use it to prove stronger versions of many existing theorems. Namely, for two graphs, if the product of the maximum degrees is small or if the total number of edges is small, then the graphs pack. In Chapter 3, we discuss the problem of finding k vertex-disjoint cycles in a multigraph. This problem originated from a conjecture of Erdos and has led to many different results. Corradi and Hajnal looked at a minimum degree condition. Enomoto and Wang independently looked at a minimum degree-sum condition. More recently, Kierstead, Kostochka, and Yeager characterized the extremal cases to improve these bounds. In Chapter 3, we improve on the multigraph degree-sum result. We characterize all multigraphs that have simple Ore-degree at least 4k -3 , but do not contain k vertex-disjoint cycles. Moreover, we provide a polynomial time algorithm for deciding if a graph contains k vertex-disjoint cycles. Lastly, in Chapter 4, we consider the same problem but with chorded cycles. Finkel looked at the minimum degree condition while Chiba, Fujita, Gao, and Li addressed the degree-sum condition. More recently, Molla, Santana, and Yeager improved this degree-sum result, and in Chapter 4, we will improve on this further.","abstract_has_math":false,"creators":["Yager, Derrek Jordan Dinius"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Kostochka, Alexandr","Balogh, Jozsef","Sowers, Richard","Lavrov, Mikhail"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-11-26T20:33:44Z","date_published":"2019-11-26T20:33:44Z","updated_at":"2026-07-22T22:24:44Z","subjects":["Combinatorics","Graph Theory","Extremal Graph Theory"],"languages":["en"],"rights":["Copyright 2019 Derrek Jordan Dinius Yager"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/105617","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kostochka, Alexandr","Balogh, Jozsef","Sowers, Richard","Lavrov, Mikhail"]},{"key":"dc:creator","label":"Author","values":["Yager, Derrek Jordan Dinius"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-11-26T20:33:44Z","2019-06-27","2019-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorics","Graph Theory","Extremal Graph Theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Derrek Jordan Dinius Yager"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/105617"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this dissertation, we focus on the sufficient conditions to guarantee one graph being the subgraph of another. In Chapter 2, we discuss list packing, a modification of the idea of graph packing. This is fitting one graph in the complement of another graph. Sauer and Spencer showed a sufficient bound involving maximum degrees, and this was further explored by Kaul and Kostochka to characterize all extremal cases. Bollobas and Eldridge (and independently Sauer and Spencer) developed edge sum bounds to guarantee packing. In Chapter 2, we introduce the new idea of list packing and use it to prove stronger versions of many existing theorems. Namely, for two graphs, if the product of the maximum degrees is small or if the total number of edges is small, then the graphs pack. In Chapter 3, we discuss the problem of finding k vertex-disjoint cycles in a multigraph. This problem originated from a conjecture of Erdos and has led to many different results. Corradi and Hajnal looked at a minimum degree condition. Enomoto and Wang independently looked at a minimum degree-sum condition. More recently, Kierstead, Kostochka, and Yeager characterized the extremal cases to improve these bounds. In Chapter 3, we improve on the multigraph degree-sum result. We characterize all multigraphs that have simple Ore-degree at least 4k -3 , but do not contain k vertex-disjoint cycles. Moreover, we provide a polynomial time algorithm for deciding if a graph contains k vertex-disjoint cycles. Lastly, in Chapter 4, we consider the same problem but with chorded cycles. Finkel looked at the minimum degree condition while Chiba, Fujita, Gao, and Li addressed the degree-sum condition. More recently, Molla, Santana, and Yeager improved this degree-sum result, and in Chapter 4, we will improve on this further.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Derrek Yager, accepted the attached license on 2019-06-25 at 13:46.","The student, Derrek Yager, submitted this Dissertation for approval on 2019-06-25 at 14:04.","This Dissertation was approved for publication on 2019-06-27 at 13:44.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14079 on 2019-11-26 at 12:50:06","Made available in DSpace on 2019-11-26T20:33:44Z (GMT). No. of bitstreams: 5 YAGER-DISSERTATION-2019.pdf: 1056649 bytes, checksum: 89564f99e8541eb3d338edf8647c7b71 (MD5) Source.zip: 1226432 bytes, checksum: 6b88376501a5c7108d9981d270468ecf (MD5) Elsevier_Copyright_Letter.pdf: 404771 bytes, checksum: 56b02a5abdbe9b81f867a1c1c5edc0f2 (MD5) LICENSE.txt: 4209 bytes, checksum: a34da7ebb5c58a79c93be2ba34fac8ff (MD5) Springer_Copyright_Letter.pdf: 779418 bytes, checksum: 0fa70e1d1e1b919941324c74f82d2099 (MD5) Previous issue date: 2019-06-27"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Sufficient degree conditions for graph embeddings"]}]}],"canonical_facts":{"dc:contributor":["Kostochka, Alexandr","Balogh, Jozsef","Sowers, Richard","Lavrov, Mikhail"],"dc:creator":["Yager, Derrek Jordan Dinius"],"dc:date":["2019-11-26T20:33:44Z","2019-06-27","2019-08"],"dc:description":["In this dissertation, we focus on the sufficient conditions to guarantee one graph being the subgraph of another. In Chapter 2, we discuss list packing, a modification of the idea of graph packing. This is fitting one graph in the complement of another graph. Sauer and Spencer showed a sufficient bound involving maximum degrees, and this was further explored by Kaul and Kostochka to characterize all extremal cases. Bollobas and Eldridge (and independently Sauer and Spencer) developed edge sum bounds to guarantee packing. In Chapter 2, we introduce the new idea of list packing and use it to prove stronger versions of many existing theorems. Namely, for two graphs, if the product of the maximum degrees is small or if the total number of edges is small, then the graphs pack. In Chapter 3, we discuss the problem of finding k vertex-disjoint cycles in a multigraph. This problem originated from a conjecture of Erdos and has led to many different results. Corradi and Hajnal looked at a minimum degree condition. Enomoto and Wang independently looked at a minimum degree-sum condition. More recently, Kierstead, Kostochka, and Yeager characterized the extremal cases to improve these bounds. In Chapter 3, we improve on the multigraph degree-sum result. We characterize all multigraphs that have simple Ore-degree at least 4k -3 , but do not contain k vertex-disjoint cycles. Moreover, we provide a polynomial time algorithm for deciding if a graph contains k vertex-disjoint cycles. Lastly, in Chapter 4, we consider the same problem but with chorded cycles. Finkel looked at the minimum degree condition while Chiba, Fujita, Gao, and Li addressed the degree-sum condition. More recently, Molla, Santana, and Yeager improved this degree-sum result, and in Chapter 4, we will improve on this further.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Derrek Yager, accepted the attached license on 2019-06-25 at 13:46.","The student, Derrek Yager, submitted this Dissertation for approval on 2019-06-25 at 14:04.","This Dissertation was approved for publication on 2019-06-27 at 13:44.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14079 on 2019-11-26 at 12:50:06","Made available in DSpace on 2019-11-26T20:33:44Z (GMT). No. of bitstreams: 5 YAGER-DISSERTATION-2019.pdf: 1056649 bytes, checksum: 89564f99e8541eb3d338edf8647c7b71 (MD5) Source.zip: 1226432 bytes, checksum: 6b88376501a5c7108d9981d270468ecf (MD5) Elsevier_Copyright_Letter.pdf: 404771 bytes, checksum: 56b02a5abdbe9b81f867a1c1c5edc0f2 (MD5) LICENSE.txt: 4209 bytes, checksum: a34da7ebb5c58a79c93be2ba34fac8ff (MD5) Springer_Copyright_Letter.pdf: 779418 bytes, checksum: 0fa70e1d1e1b919941324c74f82d2099 (MD5) Previous issue date: 2019-06-27"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/105617"],"dc:language":["en"],"dc:rights":["Copyright 2019 Derrek Jordan Dinius Yager"],"dc:subject":["Combinatorics","Graph Theory","Extremal Graph Theory"],"dc:title":["Sufficient degree conditions for graph embeddings"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:44Z"}