Lower General Position Sets in Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913187440361472 |
|---|---|
| author | Di Stefano, Gabriele Klavžar, Sandi Krishnakumar, Aditi Tuite, James Yero, Ismael |
| author_facet | Di Stefano, Gabriele Klavžar, Sandi Krishnakumar, Aditi Tuite, James Yero, Ismael |
| contents | A subset $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$. In this paper, we generalise a problem of M. Gardner to graph theory by introducing the \emph{lower general position number} $\gp ^-(G)$ of $G$, which is the number of vertices in a smallest maximal general position set of $G$. We show that ${\rm gp}^-(G) = 2$ if and only if $G$ contains a universal line and determine this number for several classes of graphs, including Kneser graphs $K(n,2)$, line graphs of complete graphs, and Cartesian and direct products of two complete graphs. We also prove several realisation results involving the lower general position number, the general position number and the geodetic number, and compare it with the lower version of the monophonic position number. We provide a sharp upper bound on the size of graphs with given lower general position number. Finally we demonstrate that the decision version of the lower general position problem is NP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_09965 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Lower General Position Sets in Graphs Di Stefano, Gabriele Klavžar, Sandi Krishnakumar, Aditi Tuite, James Yero, Ismael Combinatorics 05C12, 05C69, 68Q25 A subset $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$. In this paper, we generalise a problem of M. Gardner to graph theory by introducing the \emph{lower general position number} $\gp ^-(G)$ of $G$, which is the number of vertices in a smallest maximal general position set of $G$. We show that ${\rm gp}^-(G) = 2$ if and only if $G$ contains a universal line and determine this number for several classes of graphs, including Kneser graphs $K(n,2)$, line graphs of complete graphs, and Cartesian and direct products of two complete graphs. We also prove several realisation results involving the lower general position number, the general position number and the geodetic number, and compare it with the lower version of the monophonic position number. We provide a sharp upper bound on the size of graphs with given lower general position number. Finally we demonstrate that the decision version of the lower general position problem is NP-complete. |
| title | Lower General Position Sets in Graphs |
| topic | Combinatorics 05C12, 05C69, 68Q25 |
| url | https://arxiv.org/abs/2306.09965 |