Characterization of classes of graphs with large general position number
Elias John Thomas, Ullas Chandran S.V. · AKCE International Journal of Graphs and Combinatorics · 2020
Getting inspired by the famous no-three-in-line problem and by the general position subset selection problem from discrete geometry, the same is introduced into graph theory as follows. A set S of vertices in a graph G is a general position set if no element of S lies on a geodesic between any two other elements of S. The cardinality of a largest general position set is the general position number gp(G) of G. The graphs G of order n with gp(G) ∈{2,n,n−1} were already characterized. In this paper, we characterize the classes of all connected graphs of order n≥4 with the general position number n−2.