The General Position Problem: A Survey
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908823668654080 |
|---|---|
| author | V., Ullas Chandran S. Klavžar, Sandi Tuite, James |
| author_facet | V., Ullas Chandran S. Klavžar, Sandi Tuite, James |
| contents | Inspired by a chessboard puzzle of Dudeney, the general position problem in graph theory asks for a largest set $S$ of vertices in a graph such that no three elements of $S$ lie on a common shortest path. The number of vertices in such a largest set is the \emph{general position number} of the graph. This paper provides a survey of this rapidly growing problem, which now has an extensive literature. We cover exact results for various graph classes and the behaviour of the general position number under graph products and operations. We also discuss interesting variations of the general position problem, including those corresponding to different graph convexities, as well as dynamic, fractional, colouring and game versions of the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_19385 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The General Position Problem: A Survey V., Ullas Chandran S. Klavžar, Sandi Tuite, James Combinatorics 05C12, 05C69, 68Q25 Inspired by a chessboard puzzle of Dudeney, the general position problem in graph theory asks for a largest set $S$ of vertices in a graph such that no three elements of $S$ lie on a common shortest path. The number of vertices in such a largest set is the \emph{general position number} of the graph. This paper provides a survey of this rapidly growing problem, which now has an extensive literature. We cover exact results for various graph classes and the behaviour of the general position number under graph products and operations. We also discuss interesting variations of the general position problem, including those corresponding to different graph convexities, as well as dynamic, fractional, colouring and game versions of the problem. |
| title | The General Position Problem: A Survey |
| topic | Combinatorics 05C12, 05C69, 68Q25 |
| url | https://arxiv.org/abs/2501.19385 |