2020/01/07 by K., Neethu P., V., Ullas Chandran S., Changat, Manoj +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2001.02189
The general position number \rm 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 GG of G is the graph formed from the disjoint union of G and its complement G by adding the edges of a perfect matching between them. It is proved that \rm gp(GG)≤ n(G) + 1 if G is connected and \rm gp(GG)≤ n(G) if G is disconnected. Graphs G for which \rm gp(GG) = n(G) + 1 holds, provided that both G and G are connected, are characterized. A sharp lower bound on \rm gp(GG) is proved. If G is a connected bipartite graph or a split graph then \rm gp(GG)∈ \n(G), n(G)+1\. Connected bipartite graphs and block graphs for which \rm gp(GG)=n(G)+1 holds are characterized. A family of block graphs is constructed in which the \rm gp-number of their complementary prisms is arbitrary smaller than their order.