(1, 2)-rainbow connection number at most 3 in connected dense graphs
| Main Authors: | Doan, Trung Duy; School of Applied Mathematics and Informatics, Hanoi University of Science and Technology, Hanoi, Vietnam, Duyen, Le Thi; School of Applied Mathematics and Informatics, Hanoi University of Science and Technology, Hanoi, Vietnam |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2023
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/1221 https://www.ejgta.org/index.php/ejgta/article/view/1221/pdf_275 |
Daftar Isi:
- Let G be an edge-coloured 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 colours 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)| ≥ C(n − 3, 2)+7, then rc1, 2(G)≤3.