Matchings, Connectivity, and Eigenvalues in Regular Graphs

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₂ 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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• O, Suil

Contributors dc:contributor

• West, Douglas B.
• Kostochka, Alexandr V.
• Furedi, Zoltan
• Yong, Alexander

• Matching
• Connectivity
• Edge-connectivity
• Eigenvalue
• Regular graph
• Postman
• Path cover
• Average (edge)-connectivity
• Total Domination
• Balloon
• $r$-dynamic coloring

Statement dc:rights

• Copyright 2011 Suil O

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/26034

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/26034