TY - JOUR

T1 - The computational complexity of cordial and equitable labelling

AU - Cairnie, N.

AU - Edwards, K.

N1 - Copyright 2004 Elsevier Science B.V., Amsterdam. All rights reserved.

PY - 2000

Y1 - 2000

N2 - A labelling of a simple graph G = (V,E) is an assignment f of integers to the vertices of G. Under such a labelling f, we let V denote the set of vertices in G that are labelled i, and let E = {{u,?}: {u,?} ? E and |f(u) - f(?)| = j}. A k-equitable labelling of a graph G = (V,E) is a labelling f:V ? {0, 1,...,k - 1} such that, for each 0=i <j=k - 1, we have |V| -|V| ? {-1,0,1} and |E| - |E| ? {-1,0,1}. A cordial labelling of a graph G is a 2-equitable labelling of G. In this paper, we prove that the problem of deciding whether a graph G admits a cordial labelling is NP-complete, as conjectured by Kirchherr (Discrete Math. 115 (1993) 201-209). This implies that the problem of determining whether a graph G admits a k-equitable labelling is also NP-complete. A complexity result concerning another related type of labelling, known as k-cordial labelling, is also obtained.

AB - A labelling of a simple graph G = (V,E) is an assignment f of integers to the vertices of G. Under such a labelling f, we let V denote the set of vertices in G that are labelled i, and let E = {{u,?}: {u,?} ? E and |f(u) - f(?)| = j}. A k-equitable labelling of a graph G = (V,E) is a labelling f:V ? {0, 1,...,k - 1} such that, for each 0=i <j=k - 1, we have |V| -|V| ? {-1,0,1} and |E| - |E| ? {-1,0,1}. A cordial labelling of a graph G is a 2-equitable labelling of G. In this paper, we prove that the problem of deciding whether a graph G admits a cordial labelling is NP-complete, as conjectured by Kirchherr (Discrete Math. 115 (1993) 201-209). This implies that the problem of determining whether a graph G admits a k-equitable labelling is also NP-complete. A complexity result concerning another related type of labelling, known as k-cordial labelling, is also obtained.

UR - http://www.scopus.com/inward/record.url?scp=0346108634&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0346108634

SN - 0012-365X

VL - 216

SP - 29

EP - 34

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -