Characterization of classes of graphs with large general position number


Abstract in English

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 ${rm gp}(G)$ of $G.$ In cite{ullas-2016} graphs $G$ of order $n$ with ${rm gp}(G)$ $in {2, n, n-1}$ were characterized. In this paper, we characterize the classes of all connected graphs of order $ngeq 4$ with the general position number $n-2.$

Download