The general position number of digraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910139272921088 |
|---|---|
| author | V., Ullas Chandran S. Di Stefano, Gabriele Erskine, Grahame S, Haritha Thomas, Elias John Tuite, James |
| author_facet | V., Ullas Chandran S. Di Stefano, Gabriele Erskine, Grahame S, Haritha Thomas, Elias John Tuite, James |
| contents | The general position number for graphs ask for largest vertex subsets $S$ such that no three vertices are contained on a common shortest path. We examine this problem in the setting of directed graphs. We provide bounds for the general position number of digraphs, show that the problem is NP-complete for oriented graphs, investigate the problem for some important families of digraphs such as circulant digraphs, Kautz digraphs and permutation digraphs, and study the general position numbers obtained from all orientations of an undirected graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15909 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The general position number of digraphs V., Ullas Chandran S. Di Stefano, Gabriele Erskine, Grahame S, Haritha Thomas, Elias John Tuite, James Combinatorics 05C12, 05C20, 05C69 The general position number for graphs ask for largest vertex subsets $S$ such that no three vertices are contained on a common shortest path. We examine this problem in the setting of directed graphs. We provide bounds for the general position number of digraphs, show that the problem is NP-complete for oriented graphs, investigate the problem for some important families of digraphs such as circulant digraphs, Kautz digraphs and permutation digraphs, and study the general position numbers obtained from all orientations of an undirected graph. |
| title | The general position number of digraphs |
| topic | Combinatorics 05C12, 05C20, 05C69 |
| url | https://arxiv.org/abs/2604.15909 |