Rainbow connection in sparse graphs | Zendy

Arnfried Kemnitz | Zendy; Jakub Przybyło | Zendy; Ingo Schiermeyer | Zendy; Mariusz Woźniak | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Rainbow connection in sparse graphs

Author(s) -

Arnfried Kemnitz,

Jakub Przybyło,

Ingo Schiermeyer,

Mariusz Woźniak

Publication year - 2012

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1640

Subject(s) - mathematics , connection (principal bundle) , rainbow , combinatorics , geometry , physics , quantum mechanics

An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) ≤ k if |V (G)| = n and for all integers n and k with n − 6 ≤ k ≤ n − 3. We also show that this bound is tight.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research