Antitwins in partitionable graphs (Q1210574)

Given two integers \(p,q \geq 2\), a graph \(G\) with \(n=pq+1\) vertices is called \((p,q)\)-partitionable if the following conditions hold: (i) for each vertex \(x\), \(G-x\) can be partitioned into \(p\) cliques of size \(q\) and into \(q\) stable sets of size \(p\); (ii) \(G\) has \(n\) stable sets of size \(p\) and \(n\) cliques of size \(q\); (iii) each vertex \(x\) of \(G\) belongs to exactly \(p\) stable sets of size \(p\) and to \(q\) cliques of size \(q\). Two vertices \(x,y\) of a graph are called antitwins if every vertex different from \(x\) and \(y\) is adjacent to exactly one of them. The following theorem is proved here: For \(p,q \geq 5\), there exists a \((p,q)\)-partitionable graph having a pair of antitwins. For \(p,q \leq 3\), there is no \((p,q)\)-partitionable graph having antitwins, except if \(p=q=3\).