{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/26034"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/26034","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Matchings, Connectivity, and Eigenvalues in Regular Graphs","abstract":"We study extremal and structural problems in regular graphs involving various parameters. In Chapter 2, we obtain the best lower bound for the matching number over $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also establish the best upper bound for the number of cut-edges over $n$-vertex connected odd regular graphs and determine when the number of cut-edges is maximized. In addition, there is a relationship between the matching number and the total domination number in regular graphs. In Chapter 3, we explore the relationship between eigenvalue and matching number in regular graphs. We give a condition on an appropriate eigenvalue that guarantees a lower bound for the matching number of a $l$-edge-connected $d$-regular graph, when $l\\leq d-2$. We also study what is the weakest hypothesis on the second largest eigenvalue $\\lambda_2$ for a $d$-regular graph $G$ to guarantee that $G$ is $l$-edge-connected. In Chapter 4, we study several extremal problems for regular graphs, including the Chinese postman problem, the path cover number, the average edge-connectivity, and the number of perfect matchings. In Chapter 5, we study an $r$-dynamic coloring problem and give the relationship between the $r$-dynamic chromatic number and the chromatic number in regular graphs. We also study $r$-dynichromatic number of the cartesian product of paths and cycles.","abstract_html":"We study extremal and structural problems in regular graphs involving various parameters. In Chapter 2, we obtain the best lower bound for the matching number over $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also establish the best upper bound for the number of cut-edges over $n$-vertex connected odd regular graphs and determine when the number of cut-edges is maximized. In addition, there is a relationship between the matching number and the total domination number in regular graphs. In Chapter 3, we explore the relationship between eigenvalue and matching number in regular graphs. We give a condition on an appropriate eigenvalue that guarantees a lower bound for the matching number of a $l$-edge-connected $d$-regular graph, when $l\\leq d-2$. We also study what is the weakest hypothesis on the second largest eigenvalue <span class=\"etd-inline-math\">\\lambda<sub>2</sub></span> for a $d$-regular graph $G$ to guarantee that $G$ is $l$-edge-connected. In Chapter 4, we study several extremal problems for regular graphs, including the Chinese postman problem, the path cover number, the average edge-connectivity, and the number of perfect matchings. In Chapter 5, we study an $r$-dynamic coloring problem and give the relationship between the $r$-dynamic chromatic number and the chromatic number in regular graphs. We also study $r$-dynichromatic number of the cartesian product of paths and cycles.","abstract_has_math":true,"creators":["O, Suil"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B.","Kostochka, Alexandr V.","Furedi, Zoltan","Yong, Alexander"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-08-25T22:10:01Z","date_published":"2011-08-25T22:10:01Z","updated_at":"2026-07-22T22:25:26Z","subjects":["Matching","Connectivity","Edge-connectivity","Eigenvalue","Regular graph","Postman","Path cover","Average (edge)-connectivity","Total Domination","Balloon","$r$-dynamic coloring"],"languages":["en"],"rights":["Copyright 2011 Suil O"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/26034","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B.","Kostochka, Alexandr V.","Furedi, Zoltan","Yong, Alexander"]},{"key":"dc:creator","label":"Author","values":["O, Suil"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-08-25T22:10:01Z","2011-08"]},{"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":["Matching","Connectivity","Edge-connectivity","Eigenvalue","Regular graph","Postman","Path cover","Average (edge)-connectivity","Total Domination","Balloon","$r$-dynamic coloring"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Suil O"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/26034"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We study extremal and structural problems in regular graphs involving various parameters. In Chapter 2, we obtain the best lower bound for the matching number over $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also establish the best upper bound for the number of cut-edges over $n$-vertex connected odd regular graphs and determine when the number of cut-edges is maximized. In addition, there is a relationship between the matching number and the total domination number in regular graphs. In Chapter 3, we explore the relationship between eigenvalue and matching number in regular graphs. We give a condition on an appropriate eigenvalue that guarantees a lower bound for the matching number of a $l$-edge-connected $d$-regular graph, when $l\\leq d-2$. We also study what is the weakest hypothesis on the second largest eigenvalue $\\lambda_2$ for a $d$-regular graph $G$ to guarantee that $G$ is $l$-edge-connected. In Chapter 4, we study several extremal problems for regular graphs, including the Chinese postman problem, the path cover number, the average edge-connectivity, and the number of perfect matchings. In Chapter 5, we study an $r$-dynamic coloring problem and give the relationship between the $r$-dynamic chromatic number and the chromatic number in regular graphs. We also study $r$-dynichromatic number of the cartesian product of paths and cycles.","Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2011-07-14T17:42:51Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 o_suil.pdf: 816207 bytes, checksum: f6e10706cbe21ad8a707daa27f59093c (MD5)","Made available in DSpace on 2011-08-25T22:10:01Z (GMT). No. of bitstreams: 2 O_Suil.pdf: 816145 bytes, checksum: 63efe88f9773893083b1a09a6a15dfb7 (MD5) license.txt: 4054 bytes, checksum: 0e62f538300bd3bdd3311988d9cb15c3 (MD5)"]},{"key":"dc:title","label":"Title","values":["Matchings, Connectivity, and Eigenvalues in Regular Graphs"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B.","Kostochka, Alexandr V.","Furedi, Zoltan","Yong, Alexander"],"dc:creator":["O, Suil"],"dc:date":["2011-08-25T22:10:01Z","2011-08"],"dc:description":["We study extremal and structural problems in regular graphs involving various parameters. In Chapter 2, we obtain the best lower bound for the matching number over $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also establish the best upper bound for the number of cut-edges over $n$-vertex connected odd regular graphs and determine when the number of cut-edges is maximized. In addition, there is a relationship between the matching number and the total domination number in regular graphs. In Chapter 3, we explore the relationship between eigenvalue and matching number in regular graphs. We give a condition on an appropriate eigenvalue that guarantees a lower bound for the matching number of a $l$-edge-connected $d$-regular graph, when $l\\leq d-2$. We also study what is the weakest hypothesis on the second largest eigenvalue $\\lambda_2$ for a $d$-regular graph $G$ to guarantee that $G$ is $l$-edge-connected. In Chapter 4, we study several extremal problems for regular graphs, including the Chinese postman problem, the path cover number, the average edge-connectivity, and the number of perfect matchings. In Chapter 5, we study an $r$-dynamic coloring problem and give the relationship between the $r$-dynamic chromatic number and the chromatic number in regular graphs. We also study $r$-dynichromatic number of the cartesian product of paths and cycles.","Item withdrawn by Alexis Thompson (athmpsn1@illinois.edu) on 2011-07-14T17:42:51Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 o_suil.pdf: 816207 bytes, checksum: f6e10706cbe21ad8a707daa27f59093c (MD5)","Made available in DSpace on 2011-08-25T22:10:01Z (GMT). No. of bitstreams: 2 O_Suil.pdf: 816145 bytes, checksum: 63efe88f9773893083b1a09a6a15dfb7 (MD5) license.txt: 4054 bytes, checksum: 0e62f538300bd3bdd3311988d9cb15c3 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/26034"],"dc:language":["en"],"dc:rights":["Copyright 2011 Suil O"],"dc:subject":["Matching","Connectivity","Edge-connectivity","Eigenvalue","Regular graph","Postman","Path cover","Average (edge)-connectivity","Total Domination","Balloon","$r$-dynamic coloring"],"dc:title":["Matchings, Connectivity, and Eigenvalues in Regular Graphs"],"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:25:26Z"}