On general position sets in Cartesian products

2019/07/10 by Klavžar, Sandi, Patkós, Balázs, Rus, Gregor +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1907.04535

Abstract

The general position number \rm gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three distinct vertices from S lie on a common geodesic; such sets are refereed to as gp-sets of G. The general position number of cylinders P_r \square C_s is deduced. It is proved that \rm gp(C_r \square C_s)∈ \6,7\ whenever r≥ s ≥ 3, s≠ 4, and r≥ 6. A probabilistic lower bound on the general position number of Cartesian graph powers is achieved. Along the way a formula for the number of gp-sets in P_r \square P_s, where r,s≥ 2, is also determined.

Cited by

• General position sets in strong products with paths and cycles

Related

• On the general position set of two classes of graphs
• The general position problem on Kneser graphs and on some graph operations
• Characterization of classes of graphs with large general position number
• The general position number of integer lattices
• Lower General Position in Cartesian Products