1. Rainbow connectivity and rainbow criticality on graph classes
- Author
-
Aleffer Rocha, Leandro M. Zatesko, and Sheila Morais de Almeida
- Subjects
Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,Rainbow ,0102 computer and information sciences ,02 engineering and technology ,Cartesian product ,Edge (geometry) ,01 natural sciences ,Combinatorics ,symbols.namesake ,Criticality ,010201 computation theory & mathematics ,Rainbow coloring ,Path (graph theory) ,symbols ,Discrete Mathematics and Combinatorics ,Circulant matrix ,Connectivity ,Mathematics - Abstract
Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph G , denoted r c ( G ) , is the least k for which G admits a (not necessarily proper) k -edge-coloring such that between any pair of vertices there is a path whose edge colors are all distinct. When G is disconnected, we define r c ( G ) = ∞ . A graph G is rainbow critical if the deletion of any edge of G increases r c ( G ) . In this paper we determine the rainbow connection number for the shadow graphs of paths, some circulant graphs, and some Cartesian products involving cycles and paths. We also determine conditions for the rainbow criticality and non-criticality of wheels, fans, and some Cartesian products involving cycles, paths, pans, and complete graphs.
- Published
- 2022