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

摘要

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(G) of G. It is proved that S⊆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 diam(G)=2, then gp(G) is the maximum of ω(G) and the maximum order of an induced complete multipartite subgraph of the complement of G. As a consequence, gp(G) of a cograph G can be determined in polynomial time. If G is bipartite, then gp(G) ≤ α(G) with equality if diam(G) ∈ {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.