On Sum Composite Graphs and Embedding Problem

Abstract

A sum composite labeling of a $(p,q)$ graph $G=(V,E)$ is an injective function $f:V(G)\to \{1,2,\dots ,2p\}$ such that the function $f^{+}:E(G)\to C$ is also injective, where $C$ denotes the set of all composite numbers and $f^{+}$ is defined by $f^{+}(uv)=f(u)+f(v)$ for all $uv\in E(G)$. A graph $G$ is sum composite if there exists a sum composite labeling for $G$. We give some classes of sum composite graphs and some classes of graphs which are not sum composite. We prove that it is possible to embed any graph $G$ with a given property $P$ in a sum composite graph which preserves the property $P$, where $P$ is the property of being connected, eulerian, hamiltonian, or planar. We also discuss the NP-completeness of the problem of determining the chromatic number and the clique number of sum composite graphs.