Rainbow connection number and independence number of a graph

DOI10.1007/S00373-016-1704-0MaRDI QIDQ343733zbMATH OpenOpenAlexFDO

Authors Jiuying Dong, Xueliang Li

Publication date 29 November 2016

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

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

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)

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)$.

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; zbMATH DE number 6837036
• Rainbow connection numbers of Cayley graphs

Cites work

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

Cited in

(6)

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

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)