Random Rainbow Graphs
This paper is a recently published research paper on graph theory. Suppose we take a random graph with n vertices and m edges, meaning a graph evenly picked from all graphs with n edges. We call this graph G(n,m). We will then randomly color the edge with r>n colors. We define a Hamiltonian Cycle to be a path in the graph that goes through every vertex exactly once, does not repeat edges, and ends where it began. We say a path is rainbow if none of the r colors appear twice on the path. A graph is then rainbow connected if every pair of vertices are connected by a rainbow path.
This paper asks two main questions. The first is how many edges and colors do we need to say that the resulting graph has a high probability of being rainbow connected. The second is given a number t, how many edges and colors do we need to ensure with high probability that the resulting graph has at least t edge-disjoint Hamiltonian cycles, meaning t Hamiltonian cycles such that no two share a common edge. This paper succeeded in creating a lower bound for the number of edges and colors for both the edges. With a sufficiently large number of edges and colors, they succeed in partitioning the graph into subgraphs, t of which are Hamiltonian.
This paper relates to the Networks course as it is studying how network structure affects the likelihood of a certain event happening. This is the basic idea of what we have been doing the entire course with different properties that related to what we were doing. Being rainbow connected or having rainbow Hamiltonian Cycles may have applications in the future for a more applicable network structure, much like several other ideas such as weighted graphs have become applicable.
https://arxiv.org/pdf/1802.00433.pdf