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 ${rm gp}(G)$ of $G$. It is proved that $Ssubseteq V(G)$ is in general position if and only if the components of $G[S]$ are complete subgraphs, the vertices of which form an in-transitive, distance-constant partition of $S$. If ${rm diam}(G) = 2$, then ${rm gp}(G)$ is the maximum of $omega(G)$ and the maximum order of an induced complete multipartite subgraph of the complement of $G$. As a consequence, ${rm gp}(G)$ of a cograph $G$ can be determined in polynomial time. If $G$ is bipartite, then ${rm gp}(G) leq alpha(G)$ with equality if ${rm diam}(G) in {2,3}$. A formula for the general position number of the complement of an arbitrary bipartite graph is deduced and simplified for the complements of trees, of grids, and of hypercubes.
Download