Rainbow connection number and graph products
Presented by Prof. Iztok PETERIN
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs
A path in an edge colored graph $G$ is called a rainbow path if all edges have pairwise different color. Then $G$ is rainbow connected if there exists a rainbow path between every pair of vertices of $G$ and the least number of colors needed to obtain a rainbow connected graph is rainbow connection number. If we demand that there must exists a shortest rainbow path between every pair of vertices, we speak about strong rainbow connected graph and strong rainbow connection number. In this talk we consider the (strong) rainbow connection number on direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results will also be presented.
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled