Dual General Position in Lexicographic Products with a Complete First Factor

Abstract

Let G be a nonempty finite simple graph. For every m ≥ 2, we prove gp_d(K_m ∘ G) = m q_2(G), where q_2(G) is the maximum size of a set A ⊆ V(G) for which both G[A] and G[V(G) ∖ A] are complete, and set q_2(G) = 0 if no such set exists. This resolves a previously posed problem concerning a complete first factor in lexicographic products. Every nonempty dual general-position set in K_m ∘ G splits each G-layer into selected and unselected cliques. Complementation identifies each layer choice with a side of a bipartition of the complement of G. This correspondence yields the size enumerator and a classification of the maximum sets, including their number. For dense input, q_2(G) and, when one exists, a maximizing admissible side can be found in O(n²) time. The same argument extends to complete joins of nonempty noncomplete factors. This record contains the paper PDF and the complete reproducibility supplement.