Almost all random graphs are cordial
by
Anant Godbole
East Tennessee State University
Coauthors: Carl Miller, Duke University, Dan Ramras, Cornell University

A graph on n vertices is said to be cordial if there exists a labelling f of the vertex set using as equal as possible a number of zeros and ones, so that the the numbers of induced edge labellings that are zero and one differ by at most one. The edge labeling induced by vertices i, j is defined by |f(i)-f(j)|. We show that the random graph G(n, p) is cordial with probability that approaches unity provided that the edge probability does not approach one as n --> \infty.

Date received: March 30, 2001