Cordial graphs: A weaker version of graceful and harmonious graphs. (English) Zbl 0616.05056

The author introduces the notion of a cordial labelling of a finite nondirected graph \(G=(V,E)\) without loops and multiple edges by defining: A labelling f of G with \(F: V\to \{0,1\}\) and with the induced edge- labelling \[ \bar f: \begin{cases} E\to \bar N=\{0,1\} \\ \{u,v\} \to | f(u)-f(v)| \end{cases} \] is said to be a cordial labelling of G if, and only if, \(| v_ f(1)- v_ f(0)| \leq 1\), \(| e_{\bar f}(1)-e_{\bar f}(0)| \leq 1\), where \(v_ f(i)\) and \(e_{\bar f}(i)\), \(i=0,1\), is the number of vertices and edges of G, respectively, with label i (under f and \(\bar f,\) respectively).
It is clear that there is a relationship between cordial graphs and graceful (harmonious) graphs. So the author demonstrates this relationship by proving that any graceful (harmonious) tree is cordial. Although he proves that every tree is cordial he isn’t able to determine the set of cordial graphs. Therefore he has to restrict himself to the determination of several special families of graphs having a cordial labelling.
Reviewer: R.Bodendiek


05C99 Graph theory