Rainbow connection number of graph power and graph products

DOI10.1007/S00373-013-1355-3MaRDI QIDQ489302zbMATH OpenOpenAlexFDO

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

Publication date 20 January 2015

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

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

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)

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.

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 connection numbers of complementary graphs
• Proper rainbow connection number of graphs

Cites work

• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• Chromatic graph theory
• Hardness and algorithms for rainbow connection
• On rainbow connection
• On the rainbow connection of Cartesian products and their subgraphs
• Rainbow connection and graph products
• Rainbow connection in graphs
• Rainbow connection number and connected dominating sets
• Rainbow connection number and connectivity
• Rainbow connection number and radius
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

Cited in

(12)

• Rainbow connection number and graph operations
• The rainbow connection number of the power graph of a finite group
• On the rainbow connection of Cartesian products and their subgraphs
• Rainbow connection number and radius
• Rainbow colouring of split graphs
• The vertex-rainbow connection number of some graph operations
• Rainbow connection number of generalized composition
• The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths
• 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)