The cordiality of one-point union of n copies of a graph

Abstract

In this paper we give an equivalent definition of a cordial graph. The definition implies a previous result of Cahit (1986); it also enables us to find infinite families of noncordial graphs, derive some bound on the number of edges in a cordial graph and establish a necessary and sufficient condition for a one-point union of two n-cliques. Let G be a rooted graph. We denote by G(n) the graph obtained from n copies of G by identifying their roots. A sufficient condition for G(n) to be cordial is related to the solution of a system involving one equation and two inequalities with their coefficients depending on some binary labellings of G. According to the solvability of the system, we are able to establish a number of necessary and sufficient conditions for the cordiality of G(n) for certain classes of G, such as cycles, complete graphs, wheels, fans and flags. © 1993.