The general position problem on Kneser graphs and on some graph operations

2019/03/11 by Ghorbani, Modjtaba, Klavžar, Sandi, Maimani, Hamid Reza +3 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1903.04286

Abstract

A vertex subset S of a graph G is a general position set of G if no vertex of S lies on a geodesic between two other vertices of S. The cardinality of a largest general position set of G is the general position number (gp-number) \rm gp(G) of G. The gp-number is determined for some families of Kneser graphs, in particular for K(n,2) and K(n,3). A sharp lower bound on the gp-number is proved for Cartesian products of graphs. The gp-number is also determined for joins of graphs, coronas over graphs, and line graphs of complete graphs.

Cited by

• General position sets in strong products with paths and cycles

Related

• On the general position problem on Kneser graphs
• Characterization of classes of graphs with large general position number
• Lower General Position Sets in Graphs
• On the general position set of two classes of graphs
• General d-position sets