Matchings, Connectivity, and Eigenvalues in Regular Graphs

O, Suil

Permalink

https://hdl.handle.net/2142/26034 Copy

Description

Title

Matchings, Connectivity, and Eigenvalues in Regular Graphs

Author(s)

O, Suil

Issue Date

2011-08-25T22:10:01Z

Director of Research (if dissertation) or Advisor (if thesis)

West, Douglas B.

Doctoral Committee Chair(s)

Kostochka, Alexandr V.

Committee Member(s)

• West, Douglas B.
• Furedi, Zoltan
• Yong, Alexander

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

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.

Graduation Semester

2011-08

Permalink

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

Copyright and License Information

Copyright 2011 Suil O

Owning Collections