Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.20189 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909366518546432 |
|---|---|
| author | Fernandes, Cristina G. Lintzmayer, Carla N. Peña, Juan P. Santos, Giovanne Trujillo-Negrete, Ana Zamora, Jose |
| author_facet | Fernandes, Cristina G. Lintzmayer, Carla N. Peña, Juan P. Santos, Giovanne Trujillo-Negrete, Ana Zamora, Jose |
| contents | For a digraph $D$ of order $n$ and an integer $1 \leq k \leq n-1$, the $k$-token digraph of $D$ is the graph 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 \setminus B$, $\{b\} = B \setminus 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20189 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A study on token digraphs Fernandes, Cristina G. Lintzmayer, Carla N. Peña, Juan P. Santos, Giovanne Trujillo-Negrete, Ana Zamora, Jose Combinatorics For a digraph $D$ of order $n$ and an integer $1 \leq k \leq n-1$, the $k$-token digraph of $D$ is the graph 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 \setminus B$, $\{b\} = B \setminus 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. |
| title | A study on token digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.20189 |