Equipartite graphs (Q1001434)

A graph \(G\) with \(2n\) vertices is said to be \textit{weakly equipartite} if, for any disjoint partition of \(V(G)\) into \(n\)-vertex sets \(A\), \(B\), vertices, the subgraphs of \(G\) induced by \(A\) and \(B\) are isomorphic; \(G\) is \textit{equipartite} if there exists an automorphism of \(G\) mapping \(A\) onto \(B\). For any graphs \(G\), \(H\) and positive integer \(n\), \(nG\) denotes a union of \(n\) vertex-disjoint copies of \(G\), and \(G \backslash H\) denotes a graph \(G\) from which the edges of a subgraph isomorphic to \(H\) have been deleted; if \(G_1\), \(G_2\) are edge-disjoint graphs sharing the same vertex-set, then \(G_1+G_2\) is their (edge-disjoint) union. \textbf{Theorem 8:} \textsl{Any disconnected, weakly equipartite graph \(G\) is one of the graphs \(2nK_1\), \(nK_2\), \(2C_4\), \(2K_n\).} \textbf{Theorem 13:} \textsl{A graph is weakly equipartite if and only if it is one of the graphs \(2nK_1\), \(nK_2\), \(2C_4\), \(K_{n,n} \backslash nK_2\), \(2K_n\), or one of their complements, \(K_{2n}\), \(K_{2n}\backslash 2K_n\), \(K_8\backslash 2C_4\), \(2K_n+nK_2\), \(K_{n,n}\).} \textbf{Corollary 14:} \textsl{A graph is equipartite if and only if it is weakly equipartite; every weakly equipartite graph is vertex-transitive.} The authors plan, in a forthcoming paper ``Equipartite polytopes'', to apply the present results to characterize equipartite polytopes, a geometric analogue of equipartite graphs.