When is the Direct Product of Generalized Mycielskians a Cover Graph

Abstract

A graph is called a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. The direct product \(G \times H\) of graphs \(G\) and \(H\) has vertex set \(V(G) \times V(H)\) and edge set \(E(G \times H) = \{ (g_i, h_s)(g_j, h_t) \mid g_ig_j \in E(G) \text{ and } h_sh_t \in E(H) \}\). We prove that the direct product \(M_m(G) \times M_n(H)\) of the generalized Mycielskians of \(G\) and \(H\) is a cover graph if and only if \(G\) or \(H\) is bipartite.