The computational complexity of cordial and equitable labelling

N. Cairnie, K. Edwards

    Research output: Contribution to journalArticlepeer-review

    37 Citations (Scopus)

    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 languageEnglish
    Pages (from-to)29-34
    Number of pages6
    JournalDiscrete Mathematics
    Volume216
    Issue number1-3
    Publication statusPublished - 2000

    Fingerprint

    Dive into the research topics of 'The computational complexity of cordial and equitable labelling'. Together they form a unique fingerprint.

    Cite this