Cordial sets of hypercubes (Q2799700)

Given a simple, finite, and connected graph \(G(V, E),\) a binary labeling \(f\) on \(V\) is friendly if the number of vertices mapped to 0 and that of those mapped to 1 differs at most 1. Given a friendly vertex labeling \(f\), the induced edge labeling \(f_\ast\) is defined by \(f_\ast(u, v)=|f(x)-f(y)|;\) and, let \(e_f(i)\) be \(|f_\ast^{-1}(i)|\), i.e., the number of edges labeled \(i\) by \(f_\ast\), a graph is cordial if, for some friendly vertex labeling \(f\), \(|e_f(1)-e_f(0)| \leq 1\).NEWLINENEWLINEThis notion of cordial labeling was suggested as a more tractable, or less demanding, characterization of graph labeling as compared to some of the others, such as graceful and harmonious labeling, although its existence was later shown to be NP-complete.NEWLINENEWLINEMore generally, the cordial set of such a graph \(G,\) denoted by \(C(G),\) is defined by \(\{|e_f(1)-e_f(0)|: \text{ where } f \text{ is friendly}\}\). Thus, a graph is cordial if either 0 or 1 is a member of \(C(G)\).NEWLINENEWLINECertain cordial set related results are derived in this paper for the \(n\)-dimensional hypercube, often denoted by \(Q_n\), perhaps one of the most studied and utilized interconnection structures.NEWLINENEWLINEIt is proved in this paper that \(Q_n\), \(n \geq 2\), is cordial\ (\(Q_1\) is trivially cordial). Moreover, cordial sets are identified for \(Q_n\), \(n \in \{2, 3, 4\}\); and a conjecture has also been made for \(Q_n\), \(n \geq 3\), which was proved in the smaller cases, and verified by a computer based demonstration when \(n=5\).