Menu
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.