We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
(1, 2)-rainbow connection number at most 3 in connected dense graphs.
- Authors
Trung Duy Doan; Le Thi Duyen
- Abstract
Let G be an edge-colored connected graph G. A path P in the graph G is called l-rainbow path if each subpath of length at most l + 1 is rainbow. The graph G is called (k, l)-rainbow connected if any two vertices in G are connected by at least k pairwise internally vertex-disjoint l-rainbow paths. The smallest number of colors needed in order to make G (k, l)-rainbow connected is called the (k, l)-rainbow connection number of G and denoted by rck,l(G). In this paper, we consider the (1, 2)-rainbow connection number at most 3 in some connected dense graphs. Our main results are as follows: (1) Let n ≥ 7 be an integer and G be a connected graph of order n. If ω(G) ≥ n - 3, then rc1,2(G) ≤ 3. Moreover, the bound of the clique number is sharpness. (2) Let n ≥ 7 be an integer and G be a connected graph of order n. If |E(G)| ≥ n-3 2 + 7, then rc1,2(G) ≤ 3.
- Subjects
DENSE graphs; INTEGERS; GRAPH connectivity
- Publication
Electronic Journal of Graph Theory & Applications, 2023, Vol 11, Issue 2, p411
- ISSN
2338-2287
- Publication type
Article
- DOI
10.5614/ejgta.2023.11.2.6