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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

On graceful labeling of Jahangir graphs

Maurizio Imbesi, Carlo Pedalà
arXiv (Cornell University)
Graph Labeling and Dimension Problems
preprint

On graceful labeling of Jahangir graphs

Maurizio Imbesi, Carlo Pedalà
preprint en

Abstract

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.

arXiv (Cornell University)
Graph Labeling and Dimension Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon