Back to Search
Start Over
On edge-graceful labeling and deficiency for regular graphs
- Source :
- AKCE International Journal of Graphs and Combinatorics, Vol 15, Iss 1, Pp 105-111 (2018)
- Publication Year :
- 2018
- Publisher :
- Taylor & Francis Group, 2018.
-
Abstract
- 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
- Subjects :
- Mathematics
QA1-939
Subjects
Details
- Language :
- English
- ISSN :
- 09728600
- Volume :
- 15
- Issue :
- 1
- Database :
- Directory of Open Access Journals
- Journal :
- AKCE International Journal of Graphs and Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.f7fc9a2a72840019fe6cd3ed7ea2ae9
- Document Type :
- article
- Full Text :
- https://doi.org/10.1016/j.akcej.2018.03.002