TY - JOUR
T1 - Kernels by rainbow paths in arc-colored tournaments
AU - Bai, Yandong
AU - Li, Binlong
AU - Zhang, Shenggui
N1 - Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2020/8/15
Y1 - 2020/8/15
N2 - For an arc-colored digraph D, define its kernel by rainbow paths to be a set S of vertices such that (i) no two vertices of S are connected by a rainbow path in D, and (ii) every vertex outside S can reach S by a rainbow path in D. In this paper, we first show that it is NP-complete to decide whether an arc-colored tournament has a kernel by rainbow paths, where a tournament is an orientation of a complete graph. In addition, we show that every arc-colored n-vertex tournament with all its strongly connected k-vertex subtournaments, 3⩽k⩽n, colored with at least k−1 colors has a kernel by rainbow paths.
AB - For an arc-colored digraph D, define its kernel by rainbow paths to be a set S of vertices such that (i) no two vertices of S are connected by a rainbow path in D, and (ii) every vertex outside S can reach S by a rainbow path in D. In this paper, we first show that it is NP-complete to decide whether an arc-colored tournament has a kernel by rainbow paths, where a tournament is an orientation of a complete graph. In addition, we show that every arc-colored n-vertex tournament with all its strongly connected k-vertex subtournaments, 3⩽k⩽n, colored with at least k−1 colors has a kernel by rainbow paths.
KW - Arc-colored tournament
KW - Kernel by rainbow (properly colored) paths
UR - http://www.scopus.com/inward/record.url?scp=85076457425&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2019.11.012
DO - 10.1016/j.dam.2019.11.012
M3 - 文章
AN - SCOPUS:85076457425
SN - 0166-218X
VL - 282
SP - 14
EP - 21
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -