Rainbow connection number and independence number of a graph

DOI10.1007/S00373-016-1704-0zbMATH Open1351.05072arXiv1204.4298OpenAlexW1552361948MaRDI QIDQ343733FDOQ343733

Xueliang Li, Jiuying Dong

Publication date: 29 November 2016

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

Abstract: Let $G$ be an edge-colored connected graph. A path of $G$ is called rainbow if its every edge is colored by a distinct color. $G$ is called rainbow connected if there exists a rainbow path between every two vertices of $G$. The minimum number of colors that are needed to make $G$ rainbow connected is called the rainbow connection number of $G$, denoted by $rc(G)$. In this paper, we investigate the relation between the rainbow connection number and the independence number of a graph. We show that if $G$ is a connected graph, then $rc(G)leq2alpha(G)-1$. Two examples $G$ are given to show that the upper bound $2alpha(G)-1$ is equal to the diameter of $G$, and therefore the best possible since the diameter is a lower bound of $rc(G)$.

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

Recommendations

• The rainbow connection number of 2-connected graphs
• Rainbow connection numbers of complementary graphs
• Total rainbow connection numbers of some special graphs
• Rainbow connection number of dense graphs
• Total rainbow connection number and complementary graph
• Rainbow connection numbers and the minimum degree sum of a graph
• Bounds for the rainbow connection number of graphs
• The rainbow connectivity of a graph
• scientific article
• Rainbow connection numbers of Cayley graphs

zbMATH Keywords

independence numberconnected dominating setrainbow connection numberrainbow coloring

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• On rainbow connection
• Rainbow connections of graphs: a survey
• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Rainbow connection in graphs with minimum degree three
• Rainbow connection number and connectivity
• The rainbow connection number of 2-connected graphs
• Rainbow connection number and radius
• Bounds for the rainbow connection number of graphs
• Upper bound involving parameter \(\sigma_2\) for the rainbow connection number
• Circumferences of k-connected graphs involving independence numbers
• Rainbow connection numbers and the minimum degree sum of a graph

Cited In (6)

• Rainbow connection numbers of complementary graphs
• An upper bound for the 3-tone chromatic number of graphs with maximum degree 3
• The rainbow connection number of 2-connected graphs
• Rainbow Connection Numbers for Undirected Double-Loop Networks
• Conflict-free connection number and independence number of a graph
• Rainbow connection number and connected dominating sets

This page was built for publication: Rainbow connection number and independence number of a graph

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