DMS Combinatorics Seminar

Speaker: Stephanie Dorough (Auburn University)

Title: Rainbow Connectivity and Proper Rainbow Connectivity

Abstract: A connected graph \(G\) is rainbow connected with respect to an edge coloring of \(G\) if each pair of distinct vertices of \(G\) are joined by a rainbow path; that is, a path with no color appearing on more than one edge of the path. \(G\) is strongly rainbow connected if each pair of distinct vertices of \(G\) are joined by a rainbow geodesic, a shortest path in \(G\) between the vertices. The (strong) rainbow connection number of \(G\), denoted \(\text{(s)rc}(G)\), is the smallest number of colors in an edge coloring of \(G\) with respect to which \(G\) is (strongly) rainbow connected.

This talk will consider two more recently introduced parameters, \(\text{prc}(G)\) and \(\text{psrc}(G)\), defined as \(\text{rc}(G)\) and \(\text{src}(G)\) were, with the additional requirement that the edge colorings be proper. We will then cover some relations among the four parameters and evaluate them on some classes of graphs, including some of the theta graphs.