Existence of Prime Labeling in Structurally Extended Wheel Graphs

Abstract

A graph with $n$ vertices has a prime labeling if its vertices can be assigned distinct integers from $1$ to $n$ such that adjacent vertex labels are relatively prime. The study of prime labeling for graphs obtained through structural operations has attracted considerable attention in recent years. In this paper, we introduce and investigate a novel family of graphs derived through a systematic structural extension of the standard wheel graph. The construction process initiates with the edge subdivision of the outer cycle of the wheel graph. Subsequently, we focus on the newly inserted subdivision vertices$-$specifically those that are non-adjacent to the central apex vertex. To enhance the structural complexity, a multi-layered expansion is applied: between every pair of consecutive subdivision vertices, we introduce $k$ distinct intermediate vertices. This operation effectively generates $k$ parallel paths of length two bridging these subdivision vertices. In this study, we specifically focus on graphs constructed with $k = 1, 2, 3,$ and $4$ layers. Furthermore, we explore the labeling properties of these extended structures and analytically prove that they admit a prime labeling for every integer $n \geq 3$.