Uniformly cordial graphs (Q2495510)

A labeling of the vertices of a \((p,q)\) graph with \(\left \lfloor \frac{p}{2} \right \rfloor\) 0's and \(\left \lceil \frac{p}{2} \right \rceil\) 1's is cordial if when edge labels are determined by the sum of the labels of the endpoints modulo 2 the number of edges so labeled 0 is within one of the number of edges so labeled 1. A graph is uniformly cordial if every such vertex labeling produces a cordial labeling. The main result here is that if \(p \geq 2\) then a \((p,q)\) graph \(G\) is uniformly cordial if and only if either \(G\) is \(K_{3}\) or else \(p\) is even and \(G\) is \(K_{1,p-1}\).