General Information

---

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.

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. I was able to prove the existence of unique gluings for these types of graphs.

---

Presentations

• First Presentation

---

Additional Information

• My Mentor
  • Dr. Robert DeMarco