Rainbow Connection Numbers of Graphs, livre ebook

In 2006, Chartrand, Johns, McKeon and Zhang introduced the concept of rainbow edge-coloring. A graph G is defined as rainbow connected if every pair of vertices is linked by a path whose edges all receive distinct colors.. The rainbow connection number, rc(G), is the minimum number of colors required to achieve this property. In 2008, Krivelevich and Yuster extended the concept to vertices by introducing the rainbow vertex-connection number, rvc(G). Beyond its role as a natural combinatorial measure, rainbow connection number has applications in secure information transmission and communication network design.

This book presents the major results on rainbow connection numbers and related graph parameters. It covers upper bounds involving order, minimum degree and degree sum; relationships with radius, diameter, and independence number; results for dense, sparse and random graphs; as well as computational complexity and algorithmic aspects.

Written for graduate students and researchers, this book is of interest to readers working in graph theory, combinatorics, probability, algorithms, and computational complexity.

See 'Complements'