Rainbow Antistrong Connection in Tournaments
- PDF / 553,038 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 194 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Rainbow Antistrong Connection in Tournaments Yumei Hu1 • Yarong Wei1 Received: 23 May 2019 / Revised: 14 September 2020 / Accepted: 17 September 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract An arc-coloured digraph is rainbow antistrong connected if any two distinct vertices u, v are connected by both a forward antidirected (u, v)-trail and a forward antidirected (v, u)-trail which do not use two arcs with the same colour. The rainbow antistrong connection number of a digraph D is the minimum number of colours needed to make the digraph rainbow antistrong connected, denoted by ! racðDÞ. An arc-coloured digraph is strong rainbow antistrong connected if any two distinct vertices u, v are connected by both a forward antidirected (u, v)-geodesic trail and a forward antidirected (v, u)-geodesic trail which do not use two arcs with the same colour. The strong rainbow antistrong connection number of a digraph D, ! denoted by sracðDÞ, is the minimum number of colours needed to make the digraph strong rainbow antistrong connected. In this paper, we prove that for any antistrong ! ! tournament Tn with n vertices racðTn Þ 3 and sracðTn Þ 3, and we construct ! ! tournaments Tn with racðTn Þ ¼ sracðTn Þ ¼ 3 for every n 18. Then, we prove that ! for any antistrong tournament Tn whose diameter is at least 4, racðTn Þ 7, and we ! construct tournaments Tn whose diameter is 3 with racðTn Þ ¼ 7 for every n 5. Keywords Rainbow connected Strong rainbow connected Antistrong digraphs Tournaments
1 Introduction In this paper, we consider graphs and digraphs which are finite and simple. We refer the reader to [4, 5] for notation and terminology not explicitly defined in this paper. & Yarong Wei [email protected] Yumei Hu [email protected] 1
School of Mathematics, Tianjin University, Tianjin 300072, China
123
Graphs and Combinatorics
Given a graph G, a k-edge-colouring of G, k 1, is a mapping u: EðGÞ ! f1; . . .; kg, note that adjacent edges may receive the same colour. A path in a kedge-colouring of G is said to be rainbow if no two distinct edges have same colour. Then an edge-coloured graph ðG; uÞ is said to be rainbow connected (or, equivalently, u is a rainbow edge-colouring of G) if any two distinct vertices of G are connected by a rainbow path. The rainbow connection number of G, denoted by rc(G), is the minimum k such that there is a rainbow k-edge-coloured of G. An edge-coloured graph ðG; uÞ is said to be strong rainbow connected (or, equivalently, u is a strong rainbow edge-colouring of G) if any two distinct vertices u; v 2 VðGÞ are connected by a rainbow (u, v)-geodesic, i.e., a rainbow (u, v)-path of minimum length. The strong rainbow connection number of G, denoted by src(G), is the minimum k such that there is a strong rainbow k-edge-coloured of G. The concept of rainbow connection in graphs was introduced by Chartrand et al. in [7]. An easy observation is that dðGÞ rcðGÞ srcðGÞ where d(G) is the diameter of G. The
Data Loading...
