Even complete supersubdivision of any graph is cordial

Abstract

Let f be a function from the vertices of G to {0,1} and for each edge xy assign the label {f(x) - f(y)}. Call f a cordial labeling of G if the number of vertices labeled 0 and the number of vertices labeled 1 differ by at most 1, and the number of edges labeled 0 and the number of edges labeled 1 differ by at most 1. A graph which admits cordial labeling is called cordial graph. Cordial labeling was introduced by I. Cahit as a weaker version of graceful and harmonious labeling. The problem of deciding whether or not a graph G is cordial is an NP-complete. Niall and Keith result motivates to construct or recognize the cordial graphs in a general approach or algorithmically. In this direction, we introduce a graph operation called an even complete supersubdivision graph of a graph. An even complete supersubdivision graph of a graph G with t edges is a graph obtained from G by replacing every edge ei = uv of G, for i, 1 ≤ i ≤ t by a complete bipartite graph Kmi,ni, such a way that the end vertices u and v of ei are identified with two distinct vertices of mi-vertices part of Kmi,ni, where mi,ni ≥ 3 and at least one of the mi or ni must be even and mi, nj may vary for each edge et of G. Further, we show that every even complete supersubdivision graph of any graph admits cordial labeling. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.