Explicit Formulas and Unimodality Phenomena for General Position Polynomials
This work addresses a combinatorial graph theory problem, providing incremental results that contribute to an open problem in the field.
The paper tackles the general position problem in graphs by deriving explicit formulas for the general position polynomials of complete multipartite graphs and analyzing unimodality properties, showing log-concavity and unimodality for part sizes up to 4 but counterexamples for larger sizes, and proving unimodality retention for specific graph classes like paths and combs.
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 $Ï(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 $Ï(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 $Ï(G)$ is retained for numerous natural classes (paths, edgeless graphs, combs). This contributes to an open problem, but the general case remains unknown. Our findings support the parallel between general position polynomials and classical position-type parameters, and identify balanced multipartite graphs and coronas as promising testbeds for additional research.