General position sets in strong products with paths and cycles

2026/07/29 by Aleksander Vesel
Mathematics · #math.CO

paper · pdf

arxiv created 2026/07/29 · arxiv updated 2026/07/30

Abstract

We study general position sets in strong products involving paths and cycles. For every connected graph H and every s≥ 2, we prove that gp(P_s \boxtimes H)=2gp(H). We also determine the corresponding values when the path is replaced by C₄, C₅, or C₆, and establish a general upper bound for gp(C_s \boxtimes H). These results are then applied to strong products of two cycles. We determine several exact values, construct infinite families attaining the general upper bound, and provide counterexamples to the conjectured multiplicativity of the general position number under the strong product.

Citations

• The General Position Problem: A Survey
• Variety of general position problems in graphs
• General position polynomials
• The general position number of integer lattices
• On general position sets in Cartesian products
• On the general position problem on Kneser graphs
• The general position problem on Kneser graphs and on some graph operations
• The general position problem and strong resolving graph
• The graph theory general position problem on some interconnection\n networks

Related

• General position problems in strong and lexicographic products of graphs
• The general position problem and strong resolving graph
• On general position sets in Cartesian products
• Variety of general position problems in graphs
• General position sets, colinear sets, and Sierpiński product graphs