Characterization of general position sets and its applications to cographs and bipartite graphs

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 $\mathrm{gp}(G)$ of $G$. It is proved that $S\subseteq 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 $\mathrm{diam}(G)=2$, then $\mathrm{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, $\mathrm{gp}(G)$ of a cograph $G$ can be determined in polynomial time. If $G$ is bipartite, then $\mathrm{gp}(G)\le \alpha (G)$ with equality if $\mathrm{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.