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

Structural and extremal results in graph theory

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF LeSaulnier_Timothy.pdf (778KB) (no description provided) PDF
Title: Structural and extremal results in graph theory
Author(s): LeSaulnier, Timothy
Advisor(s): West, Douglas B.
Contributor(s): West, Douglas B.; Füredi, Zoltán; Ferrara, Michael J.
Department / Program: Mathematics
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Doctoral
Subject(s): immersion immersion-closed rainbow Ramsey theory rainbow domination rainbow edge-chromatic number rainbow decomposition acquisition acquisition-extremal
Abstract: An H-immersion is a model of a graph H in a larger graph G. Vertices of H are represented by distinct "branch" vertices in G, while edges of H are represented by edge-disjoint walks in G joining branch vertices. By the recently proved Nash-Williams Immersion Conjecture, any immersion-closed family is characterized by forbidding the presence of H-immersions for a finite number of graphs H. We off er descriptions of some immersion-closed families along with their forbidden immersion characterizations. Our principal results in this area are a characterization of graphs with no K_{2,3}-immersion, and a characterization of graphs with neither a K_{2,3}-immersion nor a K_4-immersion. We study of the maximum number of edges in an n-vertex graph with no K_t-immersion. For t≤7, we determine this maximum value. When 5≤t≤7, we characterize the graphs with no K_t-immersion having the most edges. Given an edge-colored graph, a rainbow subgraph is a subgraph whose edges have distinct colors. We show that if the edges of a graph G are colored so that at least k colors appear at each vertex, then G contains a rainbow matching of size floor(k/2). We consider the rainbow edge-chromatic number of an edge-colored graph, \chi'_r(G), which we define to be the minimum number of rainbow matchings partitioning the edge set of G. A d-tolerant edge-colored graph is one that contains no monochromatic star with d + 1 edges. We off er examples of d-tolerant n-vertex edge-colored graphs G for which \chi'_r(G)≥d/2 (n-1) and prove that \chi'_r(G)<d(d+1)nlnn for all such graphs. We study the rainbow domination number of an edge-colored graph, \widehat{\gamma}(G), which we define to be the minimum number of rainbow stars covering the vertex set of G. We generalize three bounds on the domination number of graphs. In particular, we show that \widehat{\gamma}(G) ≤d/(d+1)n for all d-tolerant n-vertex edge-colored graphs G and characterize the edge-colored graphs achieving this bound. A total acquisition move in a weighted graph G moves all weight from a vertex u to a neighboring vertex v, provided that before this move the weight on v is at least the weight on u. The total acquisition number, a_t(G), is the minimum number of vertices with positive weight that remain in G after a sequence of total acquisition moves, starting with a uniform weighting of the vertices of G. We offer an independent proof that a_t(G)≤floor((|V(G)|+1)/3) for all graphs with at least two vertices. In addition, we characterize graphs achieving this bound. If a_t(G)=(|V(G)|+1)/3 , then G\in T\cup{P_2,C_5}, where T is the family of trees that can be constructed from P_5 by iteratively growing paths with three edges from neighbors of leaves.
Issue Date: 2012-02-06
Genre: thesis
Rights Information: Some material copyright 2010 Timothy LeSaulnier.
Date Available in IDEALS: 2012-02-06
Date Deposited: 2011-12

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 271
  • Downloads this Month: 1
  • Downloads Today: 0


My Account


Access Key