All \(4\)-Stars are Skolem-Graceful

Abstract

In this paper, we give two constructive proofs that all \(4\)-stars are Skolem-graceful. A \(4\)-star is a graph with 4 components, with at most one vertex of degree exceeding 1 per component. A graph \(G = (V, E)\) is Skolem-graceful if its vertices can be labelled \(1, 2, \ldots, |V|\) so that the edges are labelled \(1, 2, \ldots, |E|\), where each edge-label is the absolute difference of the labels of the two end-vertices. Skolem-gracefulness is related to the classic concept of gracefulness, and the methods we develop here may be useful there.