On the rainbow connection of Cartesian products and their subgraphs | Zendy

Sandi Klavžar | Zendy; Gašper Mekiš | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the rainbow connection of Cartesian products and their subgraphs

Author(s) -

Sandi Klavžar,

Gašper Mekiš

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

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

Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called -coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.

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