Gap-vertex labellings of generalized Petersen graphs
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\).
Authors
- Sundarrajan R.
- Murugan V.
Institutions
- Vellore Institute of Technology University (IN)
Publication Details
- Journal
- Ars Combinatoria
- Published
- 2026-11-15
- DOI
- https://doi.org/10.61091/ars168-08
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00