Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 29-34 |
| Number of pages | 6 |
| Journal | Discrete Mathematics |
| Volume | 216 |
| Issue number | 1-3 |
| Publication status | Published - 2000 |