2025-11-23T03:37:16.288381

Moving through Cartesian products, coronas and joins in general position

Klavžar, Krishnakumar, Kuziak et al.
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 \emph{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.
academic

Moving through Cartesian products, coronas and joins in general position

Basic Information

  • Paper ID: 2505.00535
  • Title: Moving through Cartesian products, coronas and joins in general position
  • Authors: Sandi Klavžar, Aditi Krishnakumar, Dorota Kuziak, Ethan Shallcross, James Tuite, Ismael G. Yero
  • Classification: math.CO (Combinatorics)
  • Publication Date: October 16, 2025 (arXiv version)
  • Paper Link: https://arxiv.org/abs/2505.00535

Abstract

The general position problem seeks to find large vertex sets such that no three vertices in the set lie on the same shortest path. A dynamic version of this problem, termed the moving general position problem, was recently defined, in which a group of robots must visit all vertices of a graph while maintaining general position. This paper investigates this problem in the context of Cartesian products, coronas, and joins, providing upper and lower bounds for general graphs as well as exact values for graph families including grids, cylinders, Hamming graphs, and tree prisms.

Research Background and Motivation

Problem Origins

  1. Static General Position Problem: Originating from Dudeney's geometric puzzle, it seeks the maximum vertex set in a graph such that no three vertices in the set lie on the same shortest path
  2. Robot Communication Applications: Assuming robots communicate via shortest paths, to avoid signal interference, it is necessary to ensure no robot lies on the shortest path between two other robots
  3. Dynamic Requirements: Robot navigation in real-world scenarios is dynamic, requiring movement through networks, which motivates consideration of the moving version of the general position problem

Research Significance

  1. Theoretical Value: Extends the scope of the general position problem in traditional graph theory from static to dynamic settings
  2. Practical Applications: Provides theoretical foundations for path planning and coordination of mobile robots
  3. Graph Structure Analysis: Deepens understanding of graph structures through studying moving general position numbers under different graph product operations

Core Contributions

  1. Establishing Foundational Theoretical Framework: Provides systematic upper and lower bounds for moving general position numbers in Cartesian products, coronas, and join graphs
  2. Computing Exact Values: Derives exact formulas for moving general position numbers of several important graph families, including:
    • Cartesian products of complete graphs: Mobgp(Kn□Km)\text{Mobgp}(K_n \square K_m)
    • Grid graphs: Mobgp(Pn□Pm)=3\text{Mobgp}(P_n \square P_m) = 3 (when n,m≥3n,m \geq 3)
    • Tree prisms: Mobgp(T□K2)=ℓ(T)\text{Mobgp}(T \square K_2) = \ell(T) (number of leaves)
    • Partial results for cylinder and torus graphs
  3. Tightness Analysis of Bounds: Proves tightness of proposed bounds and provides specific graph families achieving these bounds
  4. Algorithmic Construction: Constructs concrete moving general position sets and movement sequences for multiple graph families

Detailed Methodology

Task Definition

General Position Set: A vertex subset SS of graph GG is called a general position set if no three vertices in SS lie on the same shortest path in GG.

Moving General Position Set: A set SS is called a moving general position set if, starting from SS, there exists a sequence of legal moves such that every vertex of the graph is visited by some robot at least once.

Legal Move: A move u⇝vu \rightsquigarrow v of a robot from vertex uu to adjacent vertex vv is legal if and only if:

  1. vv currently has no robot
  2. The resulting new configuration remains a general position set

Moving General Position Number: Mobgp(G)\text{Mobgp}(G) denotes the size of the maximum moving general position set of graph GG.

Core Technical Methods

1. Bound Analysis for Cartesian Products

For Cartesian product G□HG \square H, the paper establishes two important lower bounds:

Proposition 2.1:

  • Mobgp(G□H)≥max⁡{Mobgp(G),Mobgp(H)}\text{Mobgp}(G \square H) \geq \max\{\text{Mobgp}(G), \text{Mobgp}(H)\}
  • Mobgp(G□H)≥max⁡{gpo(G),gpo(H)}\text{Mobgp}(G \square H) \geq \max\{\text{gp}^o(G), \text{gp}^o(H)\}

where gpo(G)\text{gp}^o(G) is the outer general position number.

2. Layer Analysis Technique

Utilizes the layer structure of Cartesian products (GG-layers and HH-layers) for analysis:

  • GG-layers: Subgraphs induced by V(G)×{h}V(G) \times \{h\}, denoted GhG^h
  • HH-layers: Subgraphs induced by {g}×V(H)\{g\} \times V(H), denoted gH{}^gH

3. Convexity Exploitation

Key observation: Layers in Cartesian products are convex subgraphs, meaning shortest paths within layers do not leave the layer.

4. Constructive Proof Method

For lower bound proofs, the paper employs constructive methods:

  1. Place robots in specific layers
  2. Design concrete movement sequences
  3. Verify legality of each move
  4. Prove all vertices can be visited

Technical Innovations

  1. Inter-layer Movement Strategy: Develops techniques for safely moving robots between different layers while maintaining general position property
  2. Symmetry Exploitation: Cleverly utilizes graph symmetries to simplify movement sequence design
  3. Combinatorial Geometry Insights: Connects the moving general position problem with position problems in combinatorial geometry
  4. Recursive Construction: Establishes recursive construction methods for certain graph families

Experimental Setup

Theoretical Verification Methods

As a pure mathematics paper, this work employs rigorous mathematical proofs rather than experimental verification:

  1. Constructive Proofs: Proves lower bounds through explicit construction of moving general position sets
  2. Proof by Contradiction: Proves upper bounds by assuming larger sets exist and deriving contradictions
  3. Mathematical Induction: Uses induction for certain parameterized graph families
  4. Computer-Assisted Verification: Employs computer search for verification in complex cases (e.g., torus graphs)

Analyzed Graph Families

  1. Cartesian Products of Complete Graphs: Kr□KsK_r \square K_s
  2. Cartesian Products of Paths: Pn□PmP_n \square P_m (grid graphs)
  3. Tree Prisms: T□K2T \square K_2
  4. Cylinder Graphs: Cr□PsC_r \square P_s
  5. Torus Graphs: Cr□CsC_r \square C_s
  6. Coronas: G⊙HG \odot H
  7. Joins: G∨HG \vee H

Experimental Results

Main Theoretical Results

1. Exact Values for Cartesian Products of Complete Graphs

Theorem 2.4: For n≥m≥1n \geq m \geq 1:

n & \text{if } m \in \{1,2\} \\ n + m - 3 & \text{if } m \geq 3 \end{cases}$$ #### 2. Results for Grid Graphs **Theorem 3.2**: For $n,m \geq 3$, $\text{Mobgp}(P_n \square P_m) = 3$ **Theorem 3.3**: For infinite grids, $\text{Mobgp}(P_\infty \square P_\infty) = 4$ #### 3. Tree Prisms **Theorem 3.1**: For any tree $T$ with order at least 3, $\text{Mobgp}(T \square K_2) = \ell(T)$ where $\ell(T)$ denotes the number of leaves of tree $T$. #### 4. Partial Results for Cylinder Graphs **Theorem 3.4**: For $n \geq 3$: $$\text{Mobgp}(C_n \square K_2) = \begin{cases} 3 & \text{if } n = 3 \\ 2 & \text{if } n = 4 \\ 4 & \text{otherwise} \end{cases}$$ #### 5. Bounds for Coronas **Theorem 4.1**: For arbitrary graphs $G$ and $H$: $$\max\{\text{Mobgp}(G), \text{Mobgp}(H \vee K_1)\} \leq \text{Mobgp}(G \odot H) \leq \max\{n(G), \text{gp}(H \vee K_1)\}$$ #### 6. Bounds for Join Graphs **Theorem 4.4**: If $G$ and $H$ have clique number at least 2 and are not both cliques, then: $$\min\{\omega(G), \omega(H)\} + 1 \leq \text{Mobgp}(G \vee H) \leq \omega(G) + \omega(H) - 1$$ ### Tightness of Bounds The paper proves all proposed bounds are tight through specific graph families achieving these bounds: 1. **Lower Bound Tightness**: Proved via $K_r \square P_s$ for bounds in Proposition 2.1 2. **Upper Bound Tightness**: Demonstrated through Cartesian products of star graphs and other examples 3. **Gap Analysis**: Shows the gap between moving general position number and general position number can be arbitrarily large ### Important Findings 1. **Cost of Mobility**: Moving general position number is typically strictly smaller than general position number 2. **Structure Dependency**: Moving general position number strongly depends on graph structural properties 3. **Impact of Product Operations**: Different graph product operations have different impact patterns on moving general position numbers ## Related Work ### Static General Position Problem 1. **Origins**: Dudeney's geometric problem, later introduced to graph theory by Manuel and Klavžar 2. **Cartesian Product Research**: Extensive literature studies general position sets in Cartesian products 3. **Variant Problems**: Related concepts including outer general position, lower general position, mutual visibility, etc. ### Moving Version Problem 1. **First Introduction**: Defined by Klavžar et al. in 2023 2. **Special Graph Families**: Studied families include block graphs, rooted products, Kneser graphs, unicyclic graphs, etc. 3. **Related Dynamic Problems**: Moving mutual visibility problems, etc. ### Robot Navigation Applications 1. **Mutual Visibility Problems**: Applications in robot navigation and communication 2. **Path Planning**: Related to obstacle avoidance in robot path planning 3. **Distributed Algorithms**: Related to coordination problems in distributed robot systems ## Conclusions and Discussion ### Main Conclusions 1. **Systematic Framework**: Establishes systematic theoretical framework for moving general position numbers in Cartesian products, coronas, and join graphs 2. **Exact Results**: Obtains exact values for moving general position numbers of several important graph families 3. **Complete Bounds**: Provides tight upper and lower bounds and proves their optimality 4. **Construction Methods**: Develops general methods for constructing moving general position sets ### Limitations 1. **Computational Complexity**: Does not discuss algorithmic complexity of computing moving general position numbers 2. **General Graphs**: Lacks effective computational methods for moving general position numbers of general graphs 3. **Dynamic Strategies**: Optimization of movement strategies not deeply investigated 4. **Practical Constraints**: Does not consider physical constraints in real robot systems ### Future Directions The paper proposes multiple open problems in Section 5: 1. **Non-trivial Upper Bounds for Cartesian Products**: Seek better upper bounds for $\text{Mobgp}(G \square H)$ 2. **Higher Dimensions**: Study moving general position numbers of $k$-fold Cartesian products $P_\infty^{\square k}$ 3. **Special Graph Families**: Determine exact values for cylinder graphs $C_7 \square P_s$ and $C_{10} \square P_s$ 4. **Other Graph Products**: Investigate moving general position problems for strong products and direct products 5. **Hypercubes**: Determine moving general position numbers of hypercubes ## In-Depth Evaluation ### Strengths 1. **Theoretical Depth**: Provides in-depth theoretical analysis of the moving general position problem with systematic theoretical framework 2. **Methodological Innovation**: Develops multiple analytical techniques including layer analysis, symmetry exploitation, and constructive proof methods 3. **Result Completeness**: Not only provides bounds but proves their tightness with specific examples achieving these bounds 4. **Clear Presentation**: Well-structured paper with rigorous proofs that are easy to understand and verify 5. **Problem Importance**: The studied problem has significant theoretical value and potential practical applications ### Shortcomings 1. **Algorithmic Aspects**: Lacks effective algorithms for computing moving general position numbers of general graphs 2. **Complexity Analysis**: Does not discuss computational complexity of related problems 3. **Practical Applications**: Connection with real robot systems needs further strengthening 4. **Open Problems**: Many important open problems remain unsolved ### Impact 1. **Theoretical Contribution**: Contributes new research directions to combinatorics and graph theory 2. **Methodological Value**: Provided analytical methods applicable to other related problems 3. **Application Potential**: Provides theoretical foundation for robot path planning and network optimization 4. **Research Inspiration**: Proposed open problems will inspire subsequent research ### Applicable Scenarios 1. **Robot Networks**: Coordination and path planning in multi-robot systems 2. **Sensor Networks**: Deployment and communication optimization of sensor nodes 3. **Network Security**: Design of secure communication protocols in distributed systems 4. **Graph Theory Research**: Serves as theoretical foundation for position problem research in graph theory ## References The paper cites 32 related references, primarily including: 1. **Foundational Work on General Position Problems**: Manuel & Klavžar (2018) 2. **Series of Research on General Position in Cartesian Products**: Multiple papers by Klavžar et al. 3. **Robot Navigation Related Work**: Application research by Aljohani, Sharma, et al. 4. **First Paper on Moving General Position Problem**: Klavžar et al. (2023) --- This paper provides systematic theoretical analysis of the moving general position problem with significant theoretical value in combinatorics and graph theory, while simultaneously providing theoretical foundation for practical robot navigation applications. Although some open problems remain unsolved, the theoretical framework and analytical methods established in this paper provide solid foundation for subsequent research.