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, with value zero if no such set exists. This answers the published complete-first-factor question for dual general position in lexicographic products. Apart from the empty set, every feasible product set 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 gives the exact size enumerator and classifies and counts all maximum sets. On a unit-cost word RAM, a dense n-vertex representation with O(1) adjacency queries supports computation of q_2(G) and a base witness 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.