| Texto completo | |
| Autor(es): |
Fernandes, Cristina G.
;
Lintzmayer, Carla N.
;
Pena, Juan P.
;
Santos, Giovanne
;
Trujillo-Negrete, Ana
;
Zamora, Jose
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE MATHEMATICS; v. 349, n. 5, p. 15-pg., 2026-05-01. |
| Resumo | |
For a digraph D of order nand an integer 1 < k < n - 1, the k-token digraph of D is the digraph whose vertices are all k-subsets of vertices of D and, given two such k-subsets A and B, (A, B) is an arc in the k-token digraph whenever {a} = A \ B, {b} = B \ A, and there is an arc (a, b) in D. Token digraphs are a generalization of token graphs. In this paper, we study some properties of token digraphs, including strong and unilateral connectivity, kernels, girth, circumference, and Eulerianity. We also extend some known results on the clique and chromatic numbers of k-token graphs, addressing the bidirected clique number and dichromatic number of k-token digraphs. Additionally, we prove that determining whether 2-token digraphs have a kernel is NP-complete. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). (AU) | |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |
| Processo FAPESP: | 23/03167-5 - Combinatória clássica, assintótica, quântica e geométrica |
| Beneficiário: | Yoshiharu Kohayakawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |