19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

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

Primary authors