On felicitous graphs

Abstract

A graph with n edges is called harmonious if it is possible to label the vertices with distinct numbers (modulo n) in such a way that the edge labels which are sums ofend-vertex labels are also distinct (modulo n). A generalization of harmonious graphs is felicitous graphs. In felicitous labelling distinct numbers (modulo n + 1) are used to label the vertices of a graph with n edges so that the edge labels are distinct (modulo n). We give some necessary conditions for a graph to be felicitous. Some families of graphs (cycles of order 4k, complete bipartite graphs, generalized Petersen graphs,...) are shown to be felicitous, while others (cycles of order 4k + 2, the complete graph Kitn when n≥5...) arenot. We also find that almost all graphs are not felicitous. © 1991.