Lower general position sets in graphs

Di Stefano, Gabriele (avtor), Klavžar, Sandi (avtor), Krishnakumar, Aditi (avtor), Tuite, James (avtor), Yero, Ismael G. (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: general position number, geodetic number, universal line, computational complexity, Kneser graphs, line graphs
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.01.2025
• Leto izida: 2025
• Št. strani: Str. 509-531
• Številčenje: Vol. 45, no. 2
• PID: 20.500.12556/RUL-168403
• UDK: 519.17
• ISSN pri članku: 1234-3099
• DOI: 10.7151/dmgt.2542
• COBISS.SI-ID: 232294915
• Datum objave v RUL: 11.04.2025

Gradivo je del revije

• Naslov: Discussiones mathematicae : Graph theory
• Skrajšan naslov: Discuss. Math., Graph Theory
• Založnik: Technical University Press
• ISSN: 1234-3099
• COBISS.SI-ID: 7487065

Licence

• Licenca: CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
• Opis: Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: število splošne lege, geodetsko število, univerzalna premica, računska zahtevnost, Kneserjevi grafi, grafi povezav