Kernels by rainbow paths in arc-colored tournaments

Yandong Bai; Binlong Li; Shenggui Zhang

doi:10.1016/j.dam.2019.11.012

Kernels by rainbow paths in arc-colored tournaments

Yandong Bai
, Binlong Li
, Shenggui Zhang

School of Mathematics and Statistics

Northwestern Polytechnical University Xian

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	14-21
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	282
DOIs	https://doi.org/10.1016/j.dam.2019.11.012
State	Published - 15 Aug 2020

Keywords

Arc-colored tournament
Kernel by rainbow (properly colored) paths

Access to Document

10.1016/j.dam.2019.11.012

Cite this

@article{804c5a50316e40e59d2845237a4ebe05,

title = "Kernels by rainbow paths in arc-colored tournaments",

abstract = "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.",

keywords = "Arc-colored tournament, Kernel by rainbow (properly colored) paths",

author = "Yandong Bai and Binlong Li and Shenggui Zhang",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2020",

month = aug,

day = "15",

doi = "10.1016/j.dam.2019.11.012",

language = "英语",

volume = "282",

pages = "14--21",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Kernels by rainbow paths in arc-colored tournaments

AU - Bai, Yandong

AU - Li, Binlong

AU - Zhang, Shenggui

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 - https://www.scopus.com/pages/publications/85076457425

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 -

Kernels by rainbow paths in arc-colored tournaments

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this