19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Rainbow connection number and graph products
Presented by Prof. Iztok PETERIN
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs
Content
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.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Mrs. Tanja GOLOGRANC Institute of Mathematics, Physics and Mechanics
- Mr. Gašper MEKIš Institute of Mathematics, Physics and Mechanics