On Prime Index of a Graph

Abstract

In prime labeling, vertices are labeled from 1 to n, with the condition that any two adjacent vertices have relatively prime labels. Coprime labeling maintains the same criterion as prime labeling with adjacent vertices using any set of distinct positive integers. Minimum coprime number prG, is the minimum value k for which G has coprime labeling. There are many graphs that do not possess prime labeling, and hence have coprime labeling. The primary purpose of this work is to change a coprime labeled graph into a prime graph by removing the minimum number of edges. Thus, the prime index ε(G) is the least number of edges to be removed from a coprime graph G to form a prime graph. In this study, the prime index of various graphs is determined. Also, an algorithmic way to determine the prime index of the complete graph is found.

Keywords

• prime labeling, coprime labeling, minimum coprime number, prime index