Moving through Cartesian products, coronas and joins in general position

Klavžar, Sandi (author), Krishnakumar, Aditi (author), Kuziak, Dorota (author), Shallcross, Ethan (author), Tuite, James (author), Yero, Ismael G. (author)

The general position problem asks for large sets of vertices such that no three vertices of the set lie on a common shortest path. Recently a dynamic version of this problem was defined, called the mobile general position problem, in which a collection of robots must visit all the vertices of the graph whilst remaining in general position. In this paper we investigate this problem in the context of Cartesian products, corona products and joins, giving upper and lower bounds for general graphs and exact values for families including grids, cylinders, Hamming graphs and prisms of trees.

• Language: English
• Keywords: general position set, mobile general position set, mobile general position number, robot navigation, Cartesian product graph
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2026
• Year: 2026
• Number of pages: Str. 768-780
• Numbering: Vol. 379
• PID: 20.500.12556/RUL-175550
• UDC: 519.17
• ISSN on article: 0166-218X
• DOI: 10.1016/j.dam.2025.10.041
• COBISS.SI-ID: 255697155
• Publication date in RUL: 04.11.2025

Record is a part of a journal

• Title: Discrete applied mathematics
• Shortened title: Discrete appl. math.
• Publisher: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

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: množica v splošni legi, mobilna množica v splošni legi, število mobilne splošne lege, navigacija robota, kartezični produkt grafov