Search the digital library catalog

Abstract: The general position number 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 Pr ◻ Cs is deduced. It is proved that (Cr ◻ Cs)∈{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 Pr ◻ Ps, where r,s ≥ 2, is also determined.
Keywords: general position problem, Cartesian product of graphs, paths and cycles, probabilistic constructions, exact enumeration
Published in DKUM: 27.08.2024; Views: 39; Downloads: 7
Full text (586,20 KB)
This document has many files! More...