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,\dots ,|V|$ so that the edges are labelled $1,2,\dots ,|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.