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: $\text{Mobgp}(K_n \square K_m)$
   • Grid graphs: $\text{Mobgp}(P_n \square P_m) = 3$ (when $n,m \geq 3$)
   • Tree prisms: $\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 $S$ of graph $G$ is called a general position set if no three vertices in $S$ lie on the same shortest path in $G$.

Moving General Position Set: A set $S$ is called a moving general position set if, starting from $S$, 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 \rightsquigarrow v$ of a robot from vertex $u$ to adjacent vertex $v$ is legal if and only if:

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

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

Core Technical Methods

1. Bound Analysis for Cartesian Products

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

Proposition 2.1:

• $\text{Mobgp}(G \square H) \geq \max\{\text{Mobgp}(G), \text{Mobgp}(H)\}$
• $\text{Mobgp}(G \square H) \geq \max\{\text{gp}^o(G), \text{gp}^o(H)\}$

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

2. Layer Analysis Technique

Utilizes the layer structure of Cartesian products ($G$-layers and $H$-layers) for analysis:

• $G$-layers: Subgraphs induced by $V(G) \times \{h\}$, denoted $G^h$
• $H$-layers: Subgraphs induced by $\{g\} \times V(H)$, denoted ${}^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: $K_r \square K_s$
2. Cartesian Products of Paths: $P_n \square P_m$ (grid graphs)
3. Tree Prisms: $T \square K_2$
4. Cylinder Graphs: $C_r \square P_s$
5. Torus Graphs: $C_r \square C_s$
6. Coronas: $G \odot H$
7. Joins: $G \vee H$

Experimental Results

Main Theoretical Results

1. Exact Values for Cartesian Products of Complete Graphs

Theorem 2.4: For $n \geq m \geq 1$: $\text{Mobgp}(K_n \square K_m) = \begin{cases} 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.