RT journal article
T1 Lower General Position Sets in Graphs
A1 Di Stefano, Gabriele
A1 Klavžar, Sandi
A1 Krishnakumar, Aditi
A1 Tuite, James
A1 González Yero, Ismael
A2 Matemáticas
K1 computational complexity
K1 general position number
K1 geodetic number
K1 Kneser graphs
K1 line graphs
K1 universal line
AB A subset S of vertices of a graph G is a 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 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 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.
PB University of Zielona Gora
SN 2083-5892
YR 2025
FD 2025
LK http://hdl.handle.net/10498/38042
UL http://hdl.handle.net/10498/38042
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 10-may-2026