On k-prime graphs

Abstract

In the context of a simple undirected graph GG, a kk-prime labeling refers to assigning distinct integers from the set {k,k+1,…,∣V(G)∣+k−1}\left\{k,k+1,\ldots ,| V\left(G)| +k-1\right\} to its vertices, such that adjacent vertices in GG are labeled with numbers that are relatively prime to each other. If GG has a kk-prime labeling, we say that GG is a kk-prime graph (k-PG). In this article, we characterize when a graph up to order 6 is a k-PG and characterize when a graph of order 7 is a k-PG whenever kk and k+1k+1 are not divisible by 5. Also, we find a lower bound for the independence number of a k-PG. Finally, we study when a cycle is a k-PG.

Keywords

• independence number
• prime labeling
• prime graphs
• k-prime graphs
• maximal k-prime graphs
• 05c78