Rainbow connection number of dense graphs | Zendy

Xue Liang Li | Zendy; Mengmeng Liu | Zendy; Ingo Schiermeyer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Rainbow connection number of dense graphs

Author(s) -

Xue Liang Li,

Mengmeng Liu,

Ingo Schiermeyer

Publication year - 2013

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.1692

Subject(s) - combinatorics , rainbow , mathematics , graph , connectivity , connection (principal bundle) , path (computing) , edge coloring , discrete mathematics , graph power , line graph , geometry , computer science , physics , quantum mechanics , programming language

An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we show that rc(G) ≤ 3 if |E(G)| ≥ (n-2/2) + 2, and rc(G) ≤ 4 if |E(G)| = (n-3/2) + 3. These bounds are sharp.

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