Explicit Formulas and Unimodality Phenomena for General Position Polynomials

The general position problem in graphs seeks the largest set of vertices such that no three vertices lie on a common geodesic.

Its counting refinement, the general position polynomial $\psi(G)$, asks for all such possible sets.

In this paper, We describe general position sets for several classes of graphs and provide explicit formulas for the general position polynomials of complete multipartite graphs.

We specialize to balanced complete multipartite graphs and show that for part size $r\le 4$, the polynomial $\psi(K_{r,\dots,r})$ is log-concave and unimodal for all numbers of parts, while for larger $r$, counterexamples show that these properties fail.

Finally, we analyze the corona $G\circ K_1$ and prove that unimodality of $\psi(G)$ is retained for some classes, and counterexamples exists for complete bipartite and complete multipartite graphs.

The results verify the analogy between general position polynomials and classical position-type parameters, and establish balanced multipartite graphs and coronas as potential subjects for further investigation.