On graceful labeling of Jahangir graphs
For a graph with q edges, a graceful labeling assigns distinct integers from {0,...,q} its vertices so that the absolute differences across the edges are exactly 1,...,q. A Jahangir graph J_{n,m}, with n >= 2 and m >= 3, consists of an outer cycle on nm vertices and a hub joined to m equally spaced vertices of that cycle, with q = (n+1)m edges. This family of graphs is known to be graceful. In this paper we strengthen the gracefulness property of such graphs by assigning labels to their vertices through a parametric formula. These labeled graphs have a mono tonicity property: deleting an edge from the outer cycle leaves a path whose edge differences, in the negative orientation, are strictly increasing for even n and strictly decreasing for odd n. The starting observation is that large differences admit few endpoint pairs and require adjacencies between high and low labels. This suggests a construction based on alternating two separated label sets along the outer cycle. The formula has two parity branches, each with two cases modulo 4. Applications are given for every case.
Authors
- Maurizio Imbesi (ORCID: https://orcid.org/0000-0002-1128-5203)
- Carlo Pedalà
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16570
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- preprint