Prime and Odd Prime Labelings of Broom Graphs and Some Related Graphs

Abstract

Let G be a simple graph with a finite vertex set. A prime labeling of G is a bijection assignment of natural numbers to its vertices such that every pair of adjacent vertices receives relatively prime labels. The conjecture that every tree is a prime graph remains an interesting open problem. An odd prime labeling is defined as a mapping from each vertex of G to the odd integers from 1 to 2|V(G)| − 1 under the same coprime condition. Furthermore, it has been conjectured that every prime graph also satisfies the odd prime labeling property. In this paper, we investigate prime and odd prime labelings of broom graphs and some related graphs. Broom graphs are considered because their structure combines paths and stars, forming a non-uniform tree with diverse vertex degree characteristics. This structure makes broom graphs a representative model for testing both conjectures on a class of trees that is more complex than paths or stars individually. Future work may extend this study to more complex classes of trees and attempt to establish both conjectures in a more general setting.