The computational complexity of cordial and equitable labelling

DOI10.1016/S0012-365X(99)00295-2MaRDI QIDQ1567263zbMATH OpenOpenAlexFDO

Authors Niall Cairnie, Keith Edwards

Publication date 11 December 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00295-2

zbMATH Keywords

cordial graphsequitable labellinggraph labellingNP-completeness

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

For a graph \(G=(V,E)\), a labelling \(f: V \rightarrow \{0,1,\ldots, k-1\}\) is \(k\)-equitable, if for each \(0 \leq i < j \leq k-1\), we have \(|V_i|- |V_j|\in \{-1,0,1\}\) and \(|E_i|- |E_j|\in \{-1,0,1\}\), where \(V_i\) is the set of vertices with label \(i\), and \(E_i\) is the set of edges \(\{v,w\}\) with \(|f(v) - f(w)|= i\). A 2-equitable labelling is called cordial, i.e., the vertices are partitioned into two sets of equal or almost equal size, such that (about) half of the edges are between vertices in different classes. It is shown that it is NP-complete to decide if a given graph has a cordial labelling; and hence it is also NP-complete to decide if a graph has a \(k\)-equitable labelling. As an intermediate result, the authors show that the problem, given a graph with an even number of edges, to decide if the vertices can be partitioned into two classes with exactly half of the edges from one class to the other is NP-complete.

Recommendations

• Algorithmic complexity of proper labeling problems
• Computing equilibria: a computational complexity perspective
• Complexity of (p,1)-total labelling
• scientific article; zbMATH DE number 7364985
• Graceful labeling algorithms and complexity -- a survey
• Graph labelings derived from models in distributed computing: A complete complexity classification
• Optimal labelling schemes for adjacency, comparability, and reachability
• scientific article; zbMATH DE number 1004939
• Algorithms and complexity for a class of combinatorial optimization problems with labelling
• scientific article; zbMATH DE number 4174982

Cited in

(10)

• \( \mathbb{Z}_2 \times \mathbb{Z}_2\)-cordial cycle-free hypergraphs
• On 3-total edge product cordial labeling of a carbon nanotube network
• On friendly index sets of the edge-gluing of complete graph and cycles
• Full friendly index set. I
• Cordial labeling of hypertrees
• On friendly index sets of k-galaxies
• On total edge product cordial labeling of fullerenes
• Klein cordial trees and odd cyclic cordial friendship graphs
• Cordial forests
• On friendly index sets of 2-regular graphs

This page was built for publication: The computational complexity of cordial and equitable labelling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567263)