Abstract
An edge-graceful labeling of a finite simple graph with vertices and edges is a bijection from the set of edges to the set of integers such that the vertex sums are pairwise distinct modulo , 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 , where 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.
1 Introduction and background
All graphs in this paper are finite simple, undirected, and without loops unless otherwise stated. In 1990, N. Hartsfield and G. Ringel [Citation1] introduced the concepts called antimagic labeling and antimagic graphs.
Definition 1
Let be a graph with vertices, edges, and without any isolated vertex. An antimagic edge labeling is a bijection , such that the induced vertex sum given by is injective. A graph is called antimagic if it admits an antimagic labeling. If moreover for the vertex sums are consecutive integers, we say admits an -antimagic labeling and is an -antimagic graph.
Definition 2
Let be a graph with vertices, edges, and without any isolated vertex. An edge-graceful edge labeling is a bijection , such that the induced vertex sum given by is injective. A graph is called edge-graceful if it admits an edge-graceful labeling.
Note that an -antimagic labeling is an edge-graceful labeling, and an edge-graceful labeling is necessarily an antimagic labeling.
In 1985 S.P. Lo [Citation2] introduced such notion of edge-graceful labeling. In 2005 D. Hefetz [Citation3] proved that, for an edge-graceful graph , it is still edge-graceful after adding an arbitrary even factor. In 2008, T.-M. Wang [Citation4] studied edge-graceful spectrum of graphs. Most recently M. Bača et al. [Citation5] studied the existence for -antimagic-ness of certain 3-regular graphs. Many various types of graphs have been shown to be antimagic [3–15Citation[3]Citation[4]Citation[5]Citation[6]Citation[7]Citation[8]Citation[9]Citation[10]Citation[11]Citation[12]Citation[13]Citation[14]Citation[15]] over the years. For more conjectures and open problems on various types of antimagic labeling problems, interested readers can refer to the dynamic survey article of J. Gallian [Citation16].
In this paper, we show that an odd regular graph is edge-graceful if it contains a quasi-prism factor or a claw factor. Also a more general concept called edge-graceful deficiency is introduced, and we completely determine the edge-graceful deficiency of Hamiltonian regular graphs of even degree.
2 Odd regular graphs with a quasi-prism factor
The following is a necessary condition for a graph to be an edge-graceful graph:
Lemma 3
[Citation2]
Let be a graph with vertices and edges. If is edge-graceful, then .
In 2005 D. Hefetz [Citation3] proved the following:
Lemma 4
D. Hefetz [Citation3]
Assume is a graph which is obtained from a graph by adding an arbitrary even factor. If is edge-graceful, then is edge-graceful.
According to the 2-factorization of an even regular graph by Petersen [Citation17], the edge-graceful-ness of regular graphs can be reduced to the study of that of 2-regular graphs and 3-regular graphs. D. Hefetz mentioned the following sufficient condition for edge-graceful even regular graphs:
Corollary 5
D. Hefetz [Citation3]
Assume is an even regular graph which contains a -factor consisting of , where are odd. Then is edge-graceful.
In this section we show that an odd regular graph is edge-graceful if it contains a quasi-prism factor, which is a particular 3-regular spanning subgraph. It is clear that a 3-regular graph has even number of vertices. We define quasi-prisms as follows:
Definition 6
A quasi-prism is a 3-regular graph with vertices and , which consists of the edge-disjoint union of a 1-factor and two -regular subgraphs induced by and respectively. (See .)
The generalized Petersen graphs are examples of quasi-prisms for which 2-regular subgraphs induced by and are defined as follows.
Definition 7
Let , be integers such that and . The generalized Petersen graph is defined by , and where the subscripts are taken modulo . (See .) We call an outer cycle, and an inner cycle.
Now, we are in a position to show the following:
Theorem 8
All quasi-prisms are edge-graceful.
Proof
We have a convention that the notation stands for the set of all integers between and (inclusive), namely, . Let be a quasi-prism with vertices and edges. Also let be the 3-regular graph with vertices and , which consists of the edge-disjoint union of a 1-factor and two -regular subgraphs induced by and respectively. We denote by and these two -regular subgraphs induced by and respectively and denote the edge set of the 1-factor by . In the following in order to obtain the required edge-graceful labeling we label edges over the 1-factor with integers within , label edges over with integers within , and label edges over with integers within .
For the purpose of labeling, we assign an orientation so that, over each connected component (connected 2-cycle) of and , the flow direction is either clockwise or counter-clockwise. Then we denote the edges of by and respectively to be the outgoing edge label from the vertex and the incoming edge label to the vertex according to the given orientation. Similarly we denote the edges of by and respectively. Note that there is a one-to-one correspondence between and , also an one-to-one correspondence between and . In fact these bijections are valid even restricted to each connected cycle with the fixed orientation.
Then we may start labeling by the following steps.
Step 1. First we label edges over the 1-factor with integers within in a bijective fashion. Then we denote and the partial vertex sums thus far at the vertices and respectively contributed by the above given edge labeling over .
Step 2. Then we label the edges over using the following rule for :
Let be the vertex sum at the vertex via adding all incident edge labels. Therefore, , hence the vertex sums over is modulo .
Step 3. We label the edges over using the following rule for :
Step 3-1. If , label the edges over using the rule:
Step 3-2. If , label the edges over using the rule:
Let be the vertex sum at the vertex via adding all incident edge labels. Therefore, it can be calculated and seen that the vertex sums over is modulo .
Finally it may be seen that, from the above steps we have the desired edge-graceful labeling and the proof is complete.
Therefore, by the above result combined with Lemma 4 by Hefetz [Citation3], one sees immediately that any odd regular graph containing a quasi-prism factor is edge-graceful.
Most recently M. Bača et al. [Citation5] showed the existence of -antimagic-ness for certain regular graphs, which are examples of edge-graceful graphs. However these results naturally lead one to ask the following general question comparing edge-graceful-ness and -antimagic-ness: Does there exist any graph which is edge-graceful but not -antimagic? As far as we know, the complete graph is not -antimagic, but is edge-graceful. This fact shows that the set of -antimagic graphs is properly contained in the set of edge-graceful graphs.
In fact it is interesting to answer the following:
Problem 9
Determine all 2-regular graphs/3-regular graphs which are not -antimagic, but are edge-graceful.
3 Odd regular graphs with a claw factor
In this section we study another sufficient condition for an edge-graceful regular graphs of odd degree, namely, containing a claw factor.
There is a well known cubic graph without any perfect matching as shown in , given by J. Petersen as a related example for the fact that if a cubic graph is bridgeless then it admits a perfect matching. It is noticed the example can be treated as a factorization of one claw factor as explained below and one degenerate 2-factor and can be shown to be edge-graceful. We extend this fact to a more general situation in the following. We define a claw factor as a spanning subgraph consisting of vertex disjoint ’s, as seen in .
We are then in a position to show the following.
Theorem 10
Let be a 3-regular graph with vertices and edges. Suppose contains a claw factor, that is, can be decomposed into the union of a claw factor and a 2-regular subgraph induced by all pendant vertices of the claws in . Then is edge-graceful.
Proof
Note that has the claw factor consisting of vertex disjoint claws, which is named as for . Let the center vertex of of degree 3 be for and all other pendant vertices be for .
We use to label the edges of 2-regular subgraph induced by all pendant vertices of the claws in , and use the rest to label the edges of the claw factor . Precisely we label the three edges of the claw by for . Therefore the vertex sum at the vertex is for , namely .
On the other hand, in order to label the edges over properly, we put orientations over each connected cycle component either clockwise or counterclockwise. Then define the outgoing edge label at the vertex by for , where is the partial vertex sum while labeling the edges of claws in , thus ranges from to . Therefore, the vertex sums over are for , namely . Combined with the vertex sums over for , that is , we may see immediately that is edge-graceful since the vertex sums reduced modulo are all distinct.
Therefore by the above result combined with Lemma 4 by Hefetz [Citation3], one concludes immediately that a regular graph of odd degree containing a claw factor is edge-graceful.
4 Edge-graceful deficiency
We define in this section a new notion edge-graceful deficiency for graphs, which is a parameter for studying those graphs which do not admit any edge-graceful labeling, and furthermore to measure how close they are away from being an edge-graceful graph.
Definition 11
The edge-graceful deficiency of a graph is defined as the minimum value of such that the one-to-one vertex labeling is edge-graceful, that is, the induced vertex sum mapping given by is injective. Therefore the edge-graceful deficiency of an edge-graceful graph is 0.
Note that a necessary condition for a graph with vertices and edges to be edge-graceful is , as deduced in Lemma 3. Thus we have the following:
Corollary 12
If the cycle is edge-graceful, then is odd.
Previously it was already proved that is edge-graceful when is odd, thus when is odd. In below we determine completely the edge-graceful deficiency of cycles. Also as a corollary the edge-graceful deficiency of Hamiltonian regular graphs of even degree is obtained.
In order to show the above results, we start with the following general observation that, every graph of order cannot be edge-graceful:
Lemma 13
Let be a graph of order . Then .
Proof
Let has edges and vertices. Assign labels to edges of graph , and suppose the existence of an edge-graceful labeling with the associated vertex-weights . Consider the sum of all vertex-weights: which is also equal to . Note that is even, but is odd, a contradiction.
As a corollary we have the following:
Corollary 14
.
The remaining part for edge-graceful deficiency of cycles is , and we prove it as follows.
Lemma 15
for .
Proof
Now we show that, with one extra edge label allowed, there exists an -antimagic labeling for , thus there exists an edge-graceful labeling for .
Let the vertex set and the edge set of be and . If the missing value is then the -antimagic labeling can be defined as follows:
Then we find that the vertex-weights form the set , and reduced modulo gives us the required result.
To summarize up, we have the following for the edge-graceful deficiency for cycles:
Theorem 16
The edge-graceful deficiency of cycles is as follows:
More generally, with the help of Theorem 16 and Lemma 4 by Hefetz [Citation3], we have the following:
Theorem 17
Let be a Hamiltonian graph of order . Then the edge-graceful deficiency of is as follows:
As a corollary we have the following example for edge-graceful deficiency of the higher dimensional toroidal grids, i.e. the Cartesian product of cycles , for each . Note that always contains a Hamiltonian cycle.
Corollary 18
Let for each . Then for the higher dimensional toroidal grid of order , one has
5 Concluding remarks
In this article, we obtain edge-graceful labeling of regular graphs with particular types of 3-factors (odd regular graphs containing pseudo-prisms). Also the edge-graceful-ness is shown for the class of odd regular graphs with claw factors, which contains the case of certain odd regular graphs without any 1-factor.
Note that in 2005 D. Hefetz [Citation3] proved that a regular graph of even degree is edge-graceful if it contains a -factor consisting of , where are odd. Therefore, it is natural to ask the following:
Problem 19
Determine the edge-graceful deficiency for the -regular graph , if or is even.
If Problem 19 is answered, then so is answered the edge-graceful deficiency for an arbitrary regular graph of even degree containing a 2-factor . More general we have the following:
Problem 20
Determine the edge-graceful deficiency for a general 2-regular/3-regular graph.
If Problem 20 is answered, then so is answered the edge-graceful deficiency for an arbitrary regular graph of even/odd degree, respectively.
Notes
Peer review under responsibility of Kalasalingam University.
References
- Hartsfield N. Ringel G. Pearls in Graph Theory 1990 Academic Press, Inc. Boston (revised version 1994)
- Lo S.P. On edge-graceful labelings of graphs Congress Numer. 50 1985 231 241
- Hefetz D. Anti-magic graphs via the combinatorial nullstellensatz J. Graph Theory 50 4 2005 263 272
- Wang T.M. Toroidal grids are antimagic Lecture Notes in Comput. Sci. 3595 2005 671 679
- Bača M. Semaničová-Feňovčíková A. Wang T.-M. Zhang G.-H. On (a,1)-vertex-antimagic edge labeling of regular graphs J. Appl. Math. 2015 2015 320616
- Miller M. Bača M. Antimagic valuations of generalized petersen graphs Australas. J. Combin. 22 2000 135 139
- Bača M. Jendrol S. Miller M. Ryan J. Antimagic labelings of generalized petersen graphs that are plane Ars Combin. 73 2004 115 128
- Barrus M.D. Antimagic labeling and canonical decomposition of graphs Inform. Process. Lett. 110 7 2010 261 263
- Cheng Y. A new class of antimagic Cartesian product graphs Discrete Math. 308 24 2008 6441 6448
- Cheng Y. Lattice grids and prisms are antimagic Theor. Comput. Sci. 374 1–3 2007 66 73
- Wang T.M. Hsiao C.C. On antimagic labeling for graph products Discrete Math. 308 2008 3624 3633
- Wang T.M. Zhang G.H. On antimagic labeling of regular graphs with particular factors J. Discrete Algorithms 23 2013 76 82
- Wong T.L. Zhu X. Antimagic labelling of vertex weighted graphs J. Graph Theory 70 3 2012 348 350
- Yilma Z.B. Antimagic properties of graphs with large maximum degree J. Graph Theory 72 4 2013 367 373
- Zhang Y. Sun X. The antimagicness of the cartesian product of graphs Theor. Comput. Sci. 410 2009 727 735
- Gallian J.A. A dynamic survey of graph labeling Electron. J. Combin. DS6 2014
- Petersen J. Die theorie der regularen graphs Acta Math. 15 1891 193 220