DIMACS
DIMACS REU 2013

General Information

me
Student: Elizabeth Field
Office: CoRE 507
School: Southern Connecticut State University
E-mail: fielde1@owls.southernct.edu
Project: Graph Gluing

Project Description

The goal of this project is to determine whether the components of a multi-component graph, \(G\), can be glued together in such a way that the resultant graph is uniquely decomposable into a collection of graphs similar to the original components. For two-component graphs, the construction of a unique gluing depends on the block degree of vertices. The block degree of a vertex \(v\in G\) is the number of additional components which the removal of \(v\) generates and is denoted by \(b_G(v)\). If \(G_i\) is a component of \(G\), we will call \(B(G_i) = \) max\(_{v\in V(G_i)}b_{G_i}(v)\) the maximum block degree of \(G_i\). We will be investigating the gluing of three-component graphs by looking at the maximum block degree of each component as well as by looking at other characteristics of the components.


Weekly Log

Week 1:
This week I met with my mentor for the first time and we discussed a general plan for the summer. I began by looking at the gluing of two-component graphs and then began to investigate the gluing of three-component graphs in which each component is a tree. I also prepared for my first presentation which can be found below.
Week 2:
I began this week by extending two cases of the gluing of two-component graphs to the gluing of three-component and \(n\)-component graphs. In one case, the maximum block degree of each component is the same and in the other case, the maximum block degree of each component is different. I spent the remainder of the week looking at the gluing of three-component graphs where only two of the components have the same maximum block degree. I was able to prove there exists a unique gluing when \(0 < B(G_1) < B(G_2) = B(G_3)\) as well as when \(B(G_1) = B(G_2)\), \(B(G_2) + 1 < B(G_3)\).
In addition to working directly on my project, I spent some time beginning to learn about the probabilistic method so that I can understand the context of my problem. This week I began to go through the first chapter of Alon and Spencer's The Probabilistic Method.
Week 3:
At the beginning of this week, I revised my proof of the existance of a unique gluing when \(0 < B(G_1) < B(G_2) = B(G_3)\) and found counterexamples to ideas I had about how to glue three-component graphs where \(0 < B(G_1) = B(G_2) = B(G_3) -1\). I then moved on and began to investigate a different characteristic of graphs which are trees: tree depth. The tree depth of a vertex is the level to which a vertex survives if you remove vertices according to the following rule: at each level, keep only those vertices of degree at least 3. Draw an edge between two vertices if they were connected in the previous level by a path which did not include any internal degree 3 or greater vertices. In the example below, the tree depth of the graph is 2, while black, red, and blue vertices have tree depths of 0, 1, and 2, respectively.
Tree Depth
After exploring the effect of gluing on tree depth, I used this characteristic to prove, in three cases, the existence of unique gluings for those two-component graphs in which the components are trees of tree depth at least 1.
Week 4:
I spent this week investigating the gluing of three-component graphs in which each component is a tree of tree depth at least one (no paths). I was able to prove the existence of unique gluings for these types of graphs.
Week 5:
Much of my time this week was spent looking at the gluing of three-component tree graphs where one, two, or all three of the components are paths. Except for some small examples where unique gluings do not appear to exist, I was able to prove the existence of unique gluings. I then began to think about the gluing of three-component graphs where the components are not necessarily trees.
Week 6:
This week I attempted to extend the results we found for three-component tree-like graphs to three-component graphs whose components are not trees. To do this, I considered the spanning trees of graphs as well as a graph's block-cut vertex tree. Unfortunately, neither of these approaches led to a generalization. One problem with these approaches is that multiple graphs can have the same spanning tree or the same block-cut vertex tree, and one graph can have multiple spanning trees. In addition to thinking about the gluing of general graphs, I spent some time thinking about the gluing of graphs with any number of tree-like components. It seems to be possible in some small cases, when all of the graphs have a different tree depth for instance, however I am still working on what happens when all of the graphs have the same tree depth. The majority of my time this week, however, was spent on editing my proofs of the cases of three-component tree-like graphs and coming up with definitions, observations, and lemmas about tree-depth.
Week 7:
As this was the last week of the domestic part of the program, I spent a good portion of my time preparing for my second presentation as well as editing and refining some of the cases. I also created a tree illustrating the cases. I spent some more time on the problem of gluing three-component general graphs.
Week 8:
We arrived at DIMATIA at Charles University in Prague Tuesday morning after a long day/night of traveling. Each day this week we attended lectures given by faculty at the University and then worked on problems related to those lectures. We also spent a good deal of time exploring Prague and experiencing Czech culture.
Week 9:
This week we attended the Midsummer Combinatorial Workshop. After the workshop talks in the mornings, we had the afternoons and evenings to work on problems, listen to more lectures, and explore more of Prague.
Week 10:
The last few days at Charles University were spent working on problems, preparing for our final presentations, and writing a report on our work of the past two weeks.

Presentations and Reports


Additional Information