20.500.12556/RUL-168403 Lower general position sets in graphs 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 ${\rm 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. general position number geodetic number universal line computational complexity Kneser graphs line graphs število splošne lege geodetsko število univerzalna premica računska zahtevnost Kneserjevi grafi grafi povezav true false true Angleški jezik Slovenski jezik Članek v reviji 2025-04-11 12:31:26 2025-04-11 12:31:30 2025-04-12 04:11:17 0000-00-00 00:00:00 2025 0 0 Str. 509-531 no. 2 Vol. 45 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-01-01 519.17 1234-3099 10.7151/dmgt.2542 232294915 DMGT-2542.pdf DMGT-2542.pdf 1 7C59CC44A1DEF3E910EF867D4ECBDA0B 4f684e4af4b39d00e1c46c7379e1ab68a21990eb5ce1cd49a37ea75a61865ad1 faed2f2a-16c0-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=201801 https://www.dmgt.uz.zgora.pl/publish/article.php?doi=2542 1 0b5485be-16bf-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=201796 Fakulteta za matematiko in fiziko 0 0 0