2026-09-20T06:56:53Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/26034 2023-07-10 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

West, Douglas B. Kostochka, Alexandr V. West, Douglas B. Furedi, Zoltan Yong, Alexander O, Suil 2011-08-25T22:10:01Z 2011-08-25T22:10:01Z 2011-08-25T22:10:01Z 2011-08 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) http://hdl.handle.net/2142/26034 en Copyright 2011 Suil O Matching Connectivity Edge-connectivity Eigenvalue Regular graph Postman Path cover Average (edge)-connectivity Total Domination Balloon $r$-dynamic coloring Matchings, Connectivity, and Eigenvalues in Regular Graphs Mathematics 1257 Mathematics 0439 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Mathematics -UIUC 10KS0439PHD