IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Matchings, Connectivity, and Eigenvalues in Regular Graphs

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/26034

Files in this item

File Description Format
PDF O_Suil.pdf (816KB) (no description provided) PDF
Title: Matchings, Connectivity, and Eigenvalues in Regular Graphs
Author(s): O, Suil
Director of Research: West, Douglas B.
Doctoral Committee Chair(s): Kostochka, Alexandr V.
Doctoral Committee Member(s): West, Douglas B.; Furedi, Zoltan; Yong, Alexander
Department / Program: Mathematics
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(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.
Issue Date: 2011-08-25
URI: http://hdl.handle.net/2142/26034
Rights Information: Copyright 2011 Suil O
Date Available in IDEALS: 2011-08-25
Date Deposited: 2011-08
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 335
  • Downloads this Month: 7
  • Downloads Today: 0

Browse

My Account

Information

Access Key