On the General Position Number of Complementary Prisms
P. K. Neethu, Ullas Chandran S.V., Manoj Changat, Sandi Klavžar · Fundamenta Informaticae · 2021
The general position number gp( G) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism G[Formula: see text] of G is the graph formed from the disjoint union of G and its complement [Formula: see text] by adding the edges of a perfect matching between them. It is proved that gp( G[Formula: see text]) ≤ n( G) + 1 if G is connected and gp( G[Formula: see text]) ≤ n( G) if G is disconnected. Graphs G for which gp( G[Formula: see text]) = n( G) + 1 holds, provided that both G and [Formula: see text] are connected, are characterized. A sharp lower bound on gp( G[Formula: see text]) is proved. If G is a connected bipartite graph or a split graph then gp( G[Formula: see text]) ∈ { n( G), n( G)+1}. Connected bipartite graphs and block graphs for which gp( G[Formula: see text]) = n( G) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.