Gap-vertex labellings of generalized Petersen graphs
Ars Combinatoria · 15.11.2026 · 168 · 123-137
DOI: 10.61091/ars168-08 ↗Kurz gefasst
Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 15.11.2026. Verfasst von Sundarrajan R. und 1 weiteren Autor:innen.
Abstract (Originalsprache)
A gap-\([q]\)-vertex labelling of a graph \(G\) is an assignment \(f:V(G)\to\{1,\ldots,q\}\) for which the gap between the largest and smallest labels in the neighbourhood of each vertex induces a proper vertex colouring. The minimum such \(q\) is the vertex-gap number \(\chi_v^g(G)\). We investigate this parameter for generalized Petersen graphs \(P(n,k)\). First, we prove that every bipartite generalized Petersen graph, equivalently every \(P(n,k)\) with \(n\) even and \(k\) odd, has vertex-gap number \(2\); this gives a complete characterization of the generalized Petersen graphs admitting a gap-\([2]\)-vertex labelling. We then construct explicit gap-\([3]\)-vertex labellings for several non-bipartite classes, including families determined by congruence conditions modulo \(4\), \(5\), and \(10\), the family \(n=2tk\) with even \(k\), the cases \(k=1\) and \(k=2\) for specified odd orders, and the family \(n=3k\) with \(k\geq3\). In each case the lower bound follows from the chromatic number, while the upper bound is established by an explicit labelling and a verification of the induced colours on the three edge types of \(P(n,k)\). The results support a natural conjecture that, apart from the exceptional graphs \(P(3,1)\) and \(P(6,2)\), every non-bipartite generalized Petersen graph has vertex-gap number \(3\).
Zitieren
APA
R., S., & V., M. (2026). Gap-vertex labellings of generalized Petersen graphs. Ars Combinatoria, 168, 123-137. https://doi.org/10.61091/ars168-08
Vancouver
R. S, V. M. Gap-vertex labellings of generalized Petersen graphs. Ars Combinatoria. 2026;168:123-137. doi:10.61091/ars168-08
BibTeX
@article{R2026,
author = {R., Sundarrajan and V., Murugan},
title = {Gap-vertex labellings of generalized Petersen graphs},
journal = {Ars Combinatoria},
year = {2026},
volume = {168},
pages = {123--137},
doi = {10.61091/ars168-08}
}
EUVIMED