(1,2)-Rainbow Connection Number and Connected Dominating Sets

In this paper, we first show that for every connected graph [Formula: see text], the [Formula: see text]-rainbow connection number [Formula: see text] is upper bounded by [Formula: see text], where [Formula: see text] is a connected two-way dominating set of [Formula: see text]. As corollaries, we obtain some upper bounds of [Formula: see text]-rainbow connection number for some special graph classes, including threshold graphs, chain graphs, circular arc graphs, AT-free graphs and interval graphs. In particular, the upper bounds for threshold graphs and interval graphs are tight. We also investigate the [Formula: see text]-rainbow connection number of [Formula: see text] when its complement graph is disconnected by using two-way dominating sets. Furthermore, we show that for every connected graph [Formula: see text], the [Formula: see text] is upper bounded by [Formula: see text], where [Formula: see text] is a connected two-way two-step dominating set of [Formula: see text]. As a corollary, we give an upper bound [Formula: see text] of the [Formula: see text]-rainbow connection number for every connected graph of order [Formula: see text] and minimum degree [Formula: see text].