On a Question of Prime Labeling of Graphs

Abstract

In the field of graph theory, the complete graph  of  vertices is a simple undirected graph such that every pair of distinct vertices is connected by a unique edge. In the present work, we introduce planar subgraph  of  with maximal number of edges . Generally,  does not admit prime labeling. We present an algorithm to obtain prime-labeled subgraphs of  . We conclude the paper by stating two conjectures based on labeling of . In particular, the planar subgraph admits anti-magic labeling but does not admit edge magic total labeling.