Affiliations: [a] Department of Mathematics, Mahatma Gandhi College, University of Kerala, Thiruvananthapuram-695004, Kerala, India. p.kneethu.pk@gmail.com, svuc.math@gmail.com | [b] Department of Futures Studies, University of Kerala, Thiruvananthapuram-695581, Kerala, India. mchangat@keralauniversity.ac.in | [c] Faculty of Mathematics and Physics, University of Ljubljana, Slovenia. sandi.klavzar@fmf.uni-lj.si
Correspondence:
[*]
Address for correspondence: Faculty of Mathematics and Physics, University of Ljubljana, Slovenia. Also affiliated at: Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia.
Abstract: 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 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 gp(GG¯) ≤ n(G) + 1 if G is connected and gp(GG¯) ≤ n(G) if G is disconnected. Graphs G for which gp(GG¯) = n(G) + 1 holds, provided that both G and G¯ are connected, are characterized. A sharp lower bound on gp(GG¯) is proved. If G is a connected bipartite graph or a split graph then gp(GG¯) ∈ {n(G), n(G)+1}. Connected bipartite graphs and block graphs for which gp(GG¯) = 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.
Keywords: general position set, complementary prism, bipartite graph, split graph, block graph
