Embedding and NP-complete Problems for Some Equitable Labelings

Abstract

A cordial labeling or an equitable labeling is a weaker version of Graceful and Harmonious labelings. At present many variants of equitable labeling are available. We discuss embedding and NP-complete problems in the context of some variants of equitable labeling such as E-cordial labeling, product cordial labeling, edge product cordial labeling, total product cordial labeling and prime cordial labeling. This work also rules out any possibility of forbidden subgraph characterizations for such labelings.

Keywords

• Graph labeling
• equitable labeling; embedding of graphs; NP-complete problems
• equitable labeling
• embedding of graphs
• NP-complete problems