Graph Labellings, Embedding And NP-Completeness Theorems

Abstract

In this paper, we establish the possibility of embedding a graph as an induced subgraph in an: elegant graph, harmonious graph, felicitous graph, cordial graph, odd-graceful graph, polychrome graph, and strongly c-harmonious graph, each with a given property, leading to prove the NP-completeness of some parameters like: chromatic number, clique number, domination number, and independence number
of these graphs.