On kernels by rainbow paths in arc-coloured digraphs
In 2018, Bai, Fujita and Zhang [Discrete Math. 341 (2018), no. 6, 1523–1533] introduced the concept of a kernel by rainbow paths (for short, RP-kernel) of an arc-coloured digraph DD, which is a subset SS of vertices of DD such that (aa) there exists no rainbow path for any pair of distinct vertices...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
De Gruyter
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/f3ab52f3569c406c930f0de214d8f182 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| id |
oai:doaj.org-article:f3ab52f3569c406c930f0de214d8f182 |
|---|---|
| record_format |
dspace |
| spelling |
oai:doaj.org-article:f3ab52f3569c406c930f0de214d8f1822021-12-05T14:10:52ZOn kernels by rainbow paths in arc-coloured digraphs2391-545510.1515/math-2021-0019https://doaj.org/article/f3ab52f3569c406c930f0de214d8f1822021-05-01T00:00:00Zhttps://doi.org/10.1515/math-2021-0019https://doaj.org/toc/2391-5455In 2018, Bai, Fujita and Zhang [Discrete Math. 341 (2018), no. 6, 1523–1533] introduced the concept of a kernel by rainbow paths (for short, RP-kernel) of an arc-coloured digraph DD, which is a subset SS of vertices of DD such that (aa) there exists no rainbow path for any pair of distinct vertices of SS, and (bb) every vertex outside SS can reach SS by a rainbow path in DD. They showed that it is NP-hard to recognize whether an arc-coloured digraph has an RP-kernel and it is NP-complete to decide whether an arc-coloured tournament has an RP-kernel. In this paper, we give the sufficient conditions for the existence of an RP-kernel in arc-coloured unicyclic digraphs, semicomplete digraphs, quasi-transitive digraphs and bipartite tournaments, and prove that these arc-coloured digraphs have RP-kernels if certain “short” cycles and certain “small” induced subdigraphs are rainbow.Li RuijuanCao YanqinZhang XinhongDe Gruyterarticlearc-coloured digraphskernelskernels by rainbow paths05c2005c1205c07MathematicsQA1-939ENOpen Mathematics, Vol 19, Iss 1, Pp 268-283 (2021) |
| institution |
DOAJ |
| collection |
DOAJ |
| language |
EN |
| topic |
arc-coloured digraphs kernels kernels by rainbow paths 05c20 05c12 05c07 Mathematics QA1-939 |
| spellingShingle |
arc-coloured digraphs kernels kernels by rainbow paths 05c20 05c12 05c07 Mathematics QA1-939 Li Ruijuan Cao Yanqin Zhang Xinhong On kernels by rainbow paths in arc-coloured digraphs |
| description |
In 2018, Bai, Fujita and Zhang [Discrete Math. 341 (2018), no. 6, 1523–1533] introduced the concept of a kernel by rainbow paths (for short, RP-kernel) of an arc-coloured digraph DD, which is a subset SS of vertices of DD such that (aa) there exists no rainbow path for any pair of distinct vertices of SS, and (bb) every vertex outside SS can reach SS by a rainbow path in DD. They showed that it is NP-hard to recognize whether an arc-coloured digraph has an RP-kernel and it is NP-complete to decide whether an arc-coloured tournament has an RP-kernel. In this paper, we give the sufficient conditions for the existence of an RP-kernel in arc-coloured unicyclic digraphs, semicomplete digraphs, quasi-transitive digraphs and bipartite tournaments, and prove that these arc-coloured digraphs have RP-kernels if certain “short” cycles and certain “small” induced subdigraphs are rainbow. |
| format |
article |
| author |
Li Ruijuan Cao Yanqin Zhang Xinhong |
| author_facet |
Li Ruijuan Cao Yanqin Zhang Xinhong |
| author_sort |
Li Ruijuan |
| title |
On kernels by rainbow paths in arc-coloured digraphs |
| title_short |
On kernels by rainbow paths in arc-coloured digraphs |
| title_full |
On kernels by rainbow paths in arc-coloured digraphs |
| title_fullStr |
On kernels by rainbow paths in arc-coloured digraphs |
| title_full_unstemmed |
On kernels by rainbow paths in arc-coloured digraphs |
| title_sort |
on kernels by rainbow paths in arc-coloured digraphs |
| publisher |
De Gruyter |
| publishDate |
2021 |
| url |
https://doaj.org/article/f3ab52f3569c406c930f0de214d8f182 |
| work_keys_str_mv |
AT liruijuan onkernelsbyrainbowpathsinarccoloureddigraphs AT caoyanqin onkernelsbyrainbowpathsinarccoloureddigraphs AT zhangxinhong onkernelsbyrainbowpathsinarccoloureddigraphs |
| _version_ |
1718371656275066880 |