On edge-graceful labeling and deficiency for regular graphs

An edge-graceful labeling of a finite simple graph with p vertices and q edges is a bijection from the set of edges to the set of integers { 1, 2, …, q } such that the vertex sums are pairwise distinct modulo p, where the vertex sum at a vertex is the sum of labels of all edges incident to such vertex. A graph is called edge-graceful if it admits an edge-graceful labeling. In 2005 Hefetz (2005) proved that a regular graph of even degree is edge-graceful if it contains a 2-factor consisting of m C n, where m, n are odd. In this article, we show that a regular graph of odd degree is edge-graceful if it contains either of two particular 3-factors, namely, a claw factor and a quasi-prism factor. We also introduce a new notion called edge-graceful deficiency, which is a parameter to measure how close a graph is away from being an edge-graceful graph. In particular the edge-graceful deficiency of a regular graph of even degree containing a Hamiltonian cycle is completely determined. Keywords: Edge-graceful, Edge-graceful deficiency, Claw factor, Quasi-prism, Hamiltonian cycle

Abstract licence: CC BY-NC-ND

16 more references, whose wording the paper’s licence keeps private.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.