Digital repository of Slovenian research organisations

Show document
A+ | A- | Help | SLO | ENG

Title:Lower general position sets in graphs
Authors:ID Di Stefano, Gabriele (Author)
ID Klavžar, Sandi (Author)
ID Krishnakumar, Aditi (Author)
ID Tuite, James (Author)
ID Yero, Ismael G. (Author)
Files:.pdf PDF - Presentation file, download (254,31 KB)
MD5: C55F911300158FB64D3DD4895121F6F9
 
URL URL - Source URL, visit https://www.dmgt.uz.zgora.pl/publish/article.php?doi=2542
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract: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.
Keywords:general position number, geodetic number, universal line, computational complexity, Kneser graphs, line graphs
Publication status:Published
Publication version:Version of Record
Publication date:01.01.2025
Year of publishing:2025
Number of pages:str. 509-531
Numbering:Vol. 45, no. 2
PID:20.500.12556/DiRROS-21947 New window
UDC:519.17
ISSN on article:1234-3099
DOI:10.7151/dmgt.2542 New window
COBISS.SI-ID:232294915 New window
Publication date in DiRROS:11.04.2025
Views:104
Downloads:49
Metadata:XML DC-XML DC-RDF
:
DI STEFANO, Gabriele, KLAVŽAR, Sandi, KRISHNAKUMAR, Aditi, TUITE, James and YERO, Ismael G., 2025, Lower general position sets in graphs. Discussiones mathematicae : Graph theory [online]. 2025. Vol. 45, no. 2, p. 509–531. [Accessed 20 April 2025]. DOI 10.7151/dmgt.2542. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=21947
Copy citation
  
Share:Bookmark and Share


Similar works from our repository:

No similar works found

Similar works from other repositories:

No similar works found

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Discussiones mathematicae : Graph theory
Shortened title:Discuss. Math., Graph Theory
Publisher:Technical University Press
ISSN:1234-3099
COBISS.SI-ID:7487065 New window

Document is financed by a project

Funder:ARRS - Slovenian Research Agency
Project number:P1-0297
Name:Teorija grafov
Funder:ARRS - Slovenian Research Agency
Project number:J1-2452
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Funder:ARRS - Slovenian Research Agency
Project number:N1-0285
Name:Metrični problemi v grafih in hipergrafih
Funder:UKRI - UK Research and Innovation
Funding programme:EPSRC
Project number:EP/W522338/1
Funder:Spanish Ministry of Science and Innovation
Project number:PID2019-105824GB-I00

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

Language:Slovenian
Keywords:število splošne lege, geodetsko število, univerzalna premica, računska zahtevnost, Kneserjevi grafi, grafi povezav


Back