Rainbow connection number of graph power and graph products

DOI10.1007/S00373-013-1355-3zbMATH Open1306.05203arXiv1104.4190OpenAlexW1963839880MaRDI QIDQ489302FDOQ489302

Manu Basavaraju, L. Sunil Chandran, Deepak Rajendraprasad, Arunselvan Ramaswamy

Publication date: 20 January 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (Note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely cartesian product, lexicographic product and strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) <= 2r(G)+c, where r(G) denotes the radius of G and c in {0,1,2}. In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [Basavaraju et. al, 2010]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight upto additive constants. The proofs are constructive and hence yield polynomial time (2 + 2/r(G))-factor approximation algorithms.

Full work available at URL: https://arxiv.org/abs/1104.4190

Recommendations

• Rainbow connection number of comb product of graphs
• Rainbow vertex-connection and graph products
• The rainbow connectivity of Cartesian product graphs
• Rainbow connection numbers of Cayley graphs
• Rainbow connection number and graph operations
• The rainbow connection number of the power graph of a finite group
• Total rainbow connection numbers of some special graphs
• Rainbow connections of graphs
• Rainbow connection numbers of complementary graphs
• Proper rainbow connection number of graphs

zbMATH Keywords

strong productCartesian productlexicographic productgraph powerrainbow coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• On rainbow connection
• Rainbow connections of graphs: a survey
• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• Title not available (Why is that?)
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Rainbow connection number and connectivity
• Chromatic graph theory
• Rainbow connection number and radius
• Rainbow connection and graph products
• On the rainbow connection of Cartesian products and their subgraphs

Cited In (11)

• Rainbow connection number and graph operations
• The rainbow connection number of the power graph of a finite group
• The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths
• Rainbow connections of graphs: a survey
• The vertex-rainbow connection number of some graph operations
• Rainbow colouring of split graphs
• Rainbow connection number of generalized composition
• Rainbow vertex-connection and graph products
• Proper connection of direct products
• Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship

This page was built for publication: Rainbow connection number of graph power and graph products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489302)