期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2018
卷号：15
期号：1
页码：105-111
DOI：10.1016/j.akcej.2018.03.002
语种：English
出版社：Elsevier
摘要：AbstractAn edge-graceful labeling of a finite simple graph withpvertices andqedges is a bijection from the set of edges to the set of integers{1,2,…,q}such that the vertex sums are pairwise distinct modulop, 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 ofmCn, wherem,nare 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.
