Source-linked AI summary
Rainbow Connection Number and Connected Dominating Sets
L. Sunil Chandran, Anita Das, Deepak Rajendraprasad, Nithin M. Varma
TL;DR
The paper seeks stronger upper bounds on rainbow connection number using connected dominating sets and their two-step extensions. It establishes bounds for special graph classes, including a tight radius-based bound for bridge-less chordal graphs.
Problem
The paper seeks improved upper bounds for rainbow connection number, including an open problem on bounding it in terms of minimum degree.
Source: §1 · p. 2Method
The paper studies weakened strengthened connected dominating-set conditions whose induced subgraph colouring can be extended with a constant number of extra colours.
Source: §1 · p. 2Results
For bridge-less chordal graphs, rc(G) ≤ 3.rad(G), with equality attained by an example; unit interval graphs with minimum degree at least 2 satisfy rc(G) = diam(G).
Source: §2 · p. 6Takeaways & Limitations
The results give rainbow-connection upper bounds close to diameter for several special graph classes, with tight examples for many of the bounds.
Source: §2 · pp. 5–6The paper reports no tight examples for AT-free or circular arc graphs and notes that their upper bounds may be improvable.
Source: §2 · p. 6
Abstract
from arXiv · showhide
Rainbow connection number rc(G) of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we show that for every connected graph G, with minimum degree at least 2, the rainbow connection number is upper bounded by {\gamma}_c(G) + 2, where {\gamma}_c(G) is the connected domination number of G. Bounds of the form diameter(G) \leq rc(G) \leq diameter(G) + c, 1 \leq c \leq 4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, AT-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G) \leq 3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds. An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree {\delta}, the rainbow connection number is upper bounded by 3n/({\delta} + 1) + 3. This solves an open problem of Schiermeyer (2009), improving the previously best known bound of 20n/{\delta} by Krivelevich and Yuster (2010). Moreover, this bound is seen to be tight up to additive factors by a construction of Caro et al. (2008).
1 Introduction
The paper investigates rainbow connection bounds through connected dominating sets, seeking a weaker condition that still permits extending a colouring with few extra colours. It develops this approach for connected two-step dominating sets and relates their size to minimum degree.
1 Introduction
- Rainbow connection number rc(G) is the minimum number of edge colours needed so every vertex pair has a path with no repeated edge colour.The paper notes that colouring each edge of a spanning tree distinctly gives the general upper bound of order(G) − 1.Source: §1 · p. 2
- A connected k-step dominating set has every vertex within distance k of it, and the paper studies strengthenings that allow its colouring to extend using a constant number of extra colours.The introduction identifies including all pendant vertices as necessary and sufficient for the connected dominating-set strengthening.Source: §1 · p. 2, §1.1 · p. 4
- The paper uses a strengthened connected two-step dominating set to address an open problem on bounding rainbow connection number in terms of minimum degree.It also reports a tight upper bound on the size of a minimum connected two-step dominating set in terms of minimum degree, yielding a radius bound that marginally improves [Erd˝os et al., 1989].Source: §1 · pp. 2–3
1.1 Preliminaries
- The preliminaries define graph distance, diameter, radius, minimum degree, and connected k-step domination, alongside the special graph classes considered later.These include interval, circular arc, AT-free, threshold, and chain graphs.Source: §1.1 · p. 4
2 Our Results
The section develops connected dominating-set bounds for rainbow connection and derives results for special graph classes and minimum-degree bounds. Its two-step domination results yield a minimum-degree upper bound that answers an open question up to an additive constant.
Theorem 1 and Corollary 3
- A connected two-way dominating set D gives rc(G) ≤ rc(G[D]) + 3; when δ(G) ≥ 2, this yields rc(G) ≤ γc(G) + 2.The argument colours G[D] first and then adds three colours outside it; pendant vertices must belong to D because their incident edges cannot share a colour.Source: §2 · p. 5
Corollaries for special graph classes
- Theorem 1 yields diameter-based upper bounds for interval, AT-free, threshold, chain, and circular arc graphs through short dominating paths, vertices, edges, or cycles.The circular arc bound is diam(G) ≤ rc(G) ≤ diam(G) + 4; interval, threshold, and chain examples attain their respective upper bounds, while an AT-free example reaches diam(G) + 2, one below its upper bound.Source: §2 · p. 6
Theorem 5
- For connected chordal graphs without bridges, rc(G) ≤ 3·rad(G), and some such graph attains equality.The proof uses induction on radius, with Theorem 1 providing the induction step.Source: §2 · p. 6
Theorem 6
- For connected unit interval graphs with minimum degree at least 2, rc(G) = diam(G), strengthening the general upper bound diam(G) + 1.The paper notes that this equality result uses a different approach from Theorem 4(i).Source: §2 · p. 6
Theorem 7
- A connected two-way two-step dominating set D satisfies rc(G) ≤ rc(G[D]) + 6.The set includes every pendant vertex, and every vertex at distance two from D has at least two neighbours at distance one from D.Source: §2 · pp. 6–7
Theorem 8 and Corollary 9
- For connected graphs of order n and minimum degree δ, Theorem 8 bounds a connected two-step dominating set D by 3(n−|N2(D)|), and, for n≥4, a connected two-way set D′ by 3n.Source: §2 · p. 7
Theorem 10
- rc(G) ≤ 3n/(δ + 1) + 3 for every connected graph of order n and minimum degree δ, improving the prior bound and answering Schiermeyer’s question up to an additive 3.The bound is tight up to additive factors by a construction of Caro et al. (2008).Source: §2 · pp. 7–8
3 Proofs
The proofs extend rainbow colourings from connected dominating sets to two-step dominating sets, then bound the size of such sets using minimum degree. Structural results for interval and circular arc graphs provide small dominating paths or cycles.
3.1 Proof of Theorem 1
- A connected two-way dominating set D gives rc(G) ≤ rc(G[D]) + 3, by extending a colouring of G[D] with three additional colours.Vertices outside D are partitioned using a spanning forest, and the added colours distinguish their links to D and to one another.Source: §3.1 · p. 8
3.2 Proof of Theorem 7
- A connected two-way two-step dominating set D gives rc(G) ≤ rc(G[D]) + 6, extending the colouring through the first and second neighbourhoods.The proof first rainbow-colours D and N1(D) together with selected vertices in N2(D), then uses two additional colours for the remaining vertices.Source: §3.2 · pp. 8–9
3.3 Proof of Theorem 8
- Every connected graph G of order n ≥ 4 and minimum degree δ has a connected two-way two-step dominating set of size at most 3n/(δ + 1) − 2.Source: §3.3 · pp. 9–10
3.4 Proof of Theorem 4
- Every non-complete interval graph has a dominating path of length at most diam(G) − 2.The proof selects a shortest path between suitable intervals at opposite ends of an interval representation.Source: §3.4 · p. 11
- Every circular arc graph that is not an interval graph has a dominating cycle of diameter at most diam(G).A minimum collection of arcs covering the circle forms the cycle; a shorter path between two of its vertices would contradict that minimality.Source: §3.4 · p. 11
Tight Examples
The examples show that several rainbow-connection bounds for graph classes are attained or nearly attained. The paper also proves sharp radius and diameter bounds for bridge-less chordal and unit interval graphs.
Tight Examples
- The interval, AT-free, threshold, and chain graph examples attain or approach the stated rainbow-connection bounds, including rc(G) = diam(G) + 1 for an interval graph.The interval example has minimum degree 2 and diameter d; the AT-free example has rc(G) = diam(G) + 2, and the threshold and chain examples have rc(G) ≥ 3 and rc(G) ≥ 4, respectively.Source: Tight Examples · pp. 11–12, Figure 1 · p. 12
3.5 Proof of Theorem 5
- Every bridge-less chordal graph G satisfies rc(G) ≤ 3·rad(G), and an example attains equality.The proof inducts on radius, using the induced subgraph on vertices at distance at most r − 1 from a central vertex and adding at most three colours.Source: §3.5 · p. 13
3.6 Proof of Theorem 6
- Every unit interval graph G with δ(G) ≥ 2 satisfies rc(G) = diam(G).The proof colours edges in a spanning subgraph built from cliques along a dominating path, using at most diam(G) colours.Source: §3.6 · pp. 13–14