The computational complexity of cordial and equitable labelling
- Cairnie, Niall
- Edwards, Keith
DOIAbstract
AbstractA 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 Vi denote the set of vertices in G that are labelled i, and let Ej={{u,v}:{u,v}∈E and |f(u)−f(v)|=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 |Vi|−|Vj|∈{−1,0,1} and |Ei|−|Ej|∈{−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. ...
Add to ORKG