Abstract
Solairaju and Chithra introduced a new type of labeling of a graph with vertices and edges called an edge odd graceful labeling if there is a bijection from the edges of the graph to the set such that, when each vertex is assigned the sum of all edges incident to it , where , the resulting vertex labels are distinct. In this paper we proved necessary and sufficient conditions for some path and cycle related graphs to be edge odd graceful such as: Friendship graphs, Wheel graph, Helm graph, Web graph, Double wheel graph, Gear graph, Fan graph, Double fan graph and Polar grid graph.
1 Introduction
The field of Graph Theory plays an important role in various areas of pure and applied sciences. Graph Labeling of a graph is an assignment of integers either to the vertices or edges or both subject to certain conditions. Graph labeling is a very powerful tool that eventually makes things in different fields very ease to be handled in mathematical way. Nowadays graph labeling has much attention from different brilliant researches in graph theory which has rigorous applications in many disciplines, e.g., communication networks, coding theory, optimal circuits layouts, astronomy, radar and graph decomposition problems. See [Citation1–Citation[2]Citation3].
We begin with simple, connected, finite, undirected graph with and .
In 1967, Rosa [Citation4] introduced a labeling of called -valuation, later on Solomon W. Golomb [Citation5] called as “graceful labeling” which is an injection from the set of vertices to the set such that when each edge is assigned the label , the resulting edge labels are distinct. A graph which admits a graceful labeling is called a graceful graph.
In 1991, Gnanajothi [Citation6] introduced a labeling of called odd graceful labeling which is an injection from the set of vertices to the set such that when each edge is assigned the label , the resulting edge labels are . A graph which admits an odd graceful labeling is called an odd graceful graph.
In 1985, Lo [Citation7] introduced a labeling of called edge graceful labeling, which is a bijection from the set of edges to the set such that the induced map from the set of vertices to given by is a bijection. A graph which admits edge graceful labeling is called an edge graceful graph.
In 2009, Solairaju and Chithra [Citation8] introduced a labeling of called edge odd graceful labeling, which is a bijection from the set of edges to the set such that the induced map from the set of vertices to given by is a bijection. A graph which admits edge odd graceful labeling is called an edge odd graceful graph.
2 Edge odd graceful labeling of friendship graph
The friendship graph , is a planar undirected graph with vertices and edges constructed by joining copies of the cycle graph with a common vertex.
Theorem 1
The friendship graph , is an edge odd graceful graph.
Proof
Using standard notation , and . There are three cases:
Case (1). Let the friendship graph , be as in and the triangles in it are . Name the center by and name the other two vertices of by . First label the outer edges, beginning from the base of triangle to the triangle by , then label the inner edges incident to the center (hub) by . Then we obtain the labels of vertices as follows
By rearranging this sequence, the pattern is clear. Now the label assigned to the vertex is given by since , we have . Therefore the friendship graph admits an edge odd graceful labeling in this case.
Case (2). Let the friendship graph , be as in . First label the inner edges of the triangles by . Second label the outer edges beginning from the base of the triangle by . The induced labels of vertices are as follows: . By rearranging this sequence, the pattern is clear . Now the label assigned to the vertex is given by since , we get
Case (3). Let the friendship graph , be as in . First label the inner edges of the triangles by . Second label the outer edges beginning from the base of the triangle to the base of the triangle by and then label the base of the triangle by 1. Hence we have the labels of are as follows: . By rearranging this sequence, the pattern is clear. Now the label assigned is given by since , we get
Illustration: The edge odd graceful labeling of the graphs , and are shown in .
3 Edge odd graceful labeling of friendship graph
The friendship graph is a planar undirected graph with vertices and edges constructed by joining copies of the cycle graph with a common vertex.
Theorem 2
The friendship graph , is an edge odd graceful graph.
Proof
Here , and , there are two cases:
Case (1): When is odd. Let the friendship graph , be as in . Label the inner edges by and the outer edges by . Thus we have the labels of vertices are as follows: , and the label of vertices are as follows . Now the label assigned to the vertex is given by , since is odd, we get .
Case (2): When is even. Let the friendship graph , be as in . Label the outer edges by and the inner edges by . Thus we have the labels of vertices are as follows , and the labels of vertices are as follows Now the label assigned to the vertex is given by since is even, we have
Illustration: The edge odd graceful labeling of graphs and are shown in .
4 Edge odd graceful labeling of friendship graph
The friendship graph is a planar undirected graph with vertices and edges constructed by joining copies of the fan graph with a common vertex.
Theorem 3
The friendship graph , is an edge odd graceful graph.
Proof
Using standard notation , and .
Case (1): When or for . Let the friendship graph , be as in .
Label the outer edges by and the inner edges by , then label middle edges by . Thus we have the labels of vertices are as follows and the labels of vertices are as follows . Now the label assigned to central vertex is given by
Case (2): When or for . The proof is very similar as in case (1), only we interchange the labels of two middle edges and in case and hence , and in case , we interchange the labels of two middle edges and and hence to avoid repeated labels of vertices.
Illustration: The edge odd graceful labeling of the graphs and are shown in .
5 Edge odd graceful labeling of wheel graph
Theorem 4
For , the wheel graph is an edge odd graceful graph.
Proof
Using standard notation , and , there are three cases:
Case (1): is even. Let the wheel graph be as in with central vertex . Move anticlockwise to label the interior edges by , then move clockwise to label the cycle edges by .
Therefore the corresponding labels of vertices will be: The label assigned to the central vertex is given by . When , we have and when , we have .
Case (2). Let the wheel graph be as in . Move clockwise to label the cycle edges by , then move anticlockwise to label the interior edges by . Therefore the corresponding labels of vertices will be
Now the label assigned to the central vertex is given by , since , we have .
Case (3): . Let the wheel graph be as in . Move anticlockwise to label the interior edges by , then move clockwise to label the cycle edges by .
Therefore the corresponding labels of vertices will be : Now the label assigned to the central vertex is given by since , we have .
Illustration: The edge odd graceful labeling of the wheel graphs and are shown in .
6 Edge odd graceful labeling of helm graph
Theorem 5
The helm is an edge odd graceful graph.
Proof
Using standard notation , and
Case (1): When is odd. Let the helm graph be as in with central vertex . First label the pendant edges by . Second label the interior edges by , then label the cycle edges by . Therefore the corresponding labels of vertices will be
Now the label assigned to the central vertex is given by , since is odd, we have .
Case (2): When is even. Let the helm graph be as in with central vertex . First label the pendant edges by . Second move anticlockwise to label the interior edges by , then label the cycle edges by .
Therefore the corresponding labels of vertices will be
. Rearranging this sequence, the pattern is clear.
The labels of the pendant vertices will be .
. The label assigned to the central vertex is given by , since is even, we get.
Illustration: The edge odd graceful labeling of the helm graphs and are shown in .
7 Edge odd graceful labeling of web graph
Theorem 6
The web graph , is an edge odd graceful graph.
Proof
Here , and . Let the web graph , be as in . First move clockwise to label the pendent edges by , then move anticlockwise to label the radial edges by , then move clockwise to label the edges of inner cycle by . Finally label the edges of the external cycle by .
Thus we have the labels of vertices are as follows:
Illustration: The edge odd graceful labeling of the web graphs and are shown in .
8 Edge odd graceful labeling of double wheel graph
The double wheel graph , consists of two cycles of vertices connected to a common hub.
Theorem 7
The double wheel graph is an edge odd graceful graph.
Proof
Using standard notation and . Let the double wheel graph be as in with central vertex . First move anticlockwise to label the inner radial edges by and the outer radial edges by , then move clockwise to label the inner cycle edges by , and the outer cycle edges by .
Therefore the labels of vertices of the inner cycle will be and the labels of vertices of the outer cycle will be Rearranging these sequences, the pattern is clear.
Lastly the label assigned to the central vertex is given by therefore when is odd, we have and when is even, we get
Illustration: The edge odd graceful labeling of the double wheel graphs and are shown in .
9 Edge odd graceful labeling of fan graph
Theorem 8
The fan graph is an edge odd graceful graph.
Proof
Using standard notation and .
Case (1): or . Let be the central vertex and be the vertices of as in . Let be defined by and , ,. Therefore labels of vertices are as follows:, ,,.
The label assigned to the central vertex is given by When , we have and when , we have thus.
Case (2): or . Let be defined as in by and , .
Therefore labels of vertices are as follows: , ,,. The label assigned to the central vertex is given by . When , we have and when , we have .
Illustration: The edge odd graceful labeling of the fan graphs, , and are shown in .
10 Edge odd graceful labeling of gear graph
The Gear graph , is the graph obtained from the wheel by inserting a vertex between any two adjacent vertices in its cycle .
Theorem 9
The gear graph is an edge odd graceful graph.
Proof
Using standard notation and . Let be defined as in by , , and ,, .
Therefore labels of vertices are as follows: The label assigned to the central vertex is given by
(i) | When , we have . |
(ii) | When , we have. |
(iii) | When , we have . |
(iv) | When , we have . |
(v) | When , we have. |
(vi) | When , we have . |
Illustration: The edge odd graceful labeling of the gear graphs , , , , and are shown in .
11 Edge odd graceful labeling of half gear graph
The half gear graph , is the graph obtained from the fan graph by inserting a vertex between any two adjacent vertices in its path .
Theorem 10
The half gear graph is an edge odd graceful graph.
Proof
Using standard notation and .
Case (1): or . Let be defined as in . By , and , , .
Therefore labels of vertices are as follows: , . The label assigned to the central vertex is given by
(i) | When , we have . |
(ii) | When , we have . |
Case (2): or . Let be defined as in . By , and , , .
Therefore labels of vertices are as follows: The label assigned to the central vertex is given by
(i) | When , we have . |
(ii) | When , we have . |
Case (3): . Let be defined as in . By , and , , , , , , .
Therefore labels of vertices are as follows The label assigned to the central vertex is given by
Since , we have .
Case (4): . Let be defined as in by , and , , , , .
Therefore labels of vertices are as follows: The label assigned to the central vertex is given by . Since , we have .
Illustration: The edge odd graceful labeling of the half gear graphs , , , , and are shown in .
12 Edge odd graceful labeling of double fan graph
Theorem 11
The double fan graph , is an edge odd graceful graph.
Proof
Using standard notation and .
Case (1): is odd or or or . Let be defined as in . By
Therefore labels of vertices are as follows . The label assigned to the central vertex is given by
(i) | When , we have |
(ii) | When , we have |
(iii) | When , we have |
(iv) | When , we have |
(v) | When , we have |
(vi) | When , we have |
The label assigned to the central vertex is given by
(i) | When , we have |
(ii) | When , we have |
(iii) | When , we have |
(iv) | When , we have |
(v) | When , we have |
(vi) | When , we have |
Case (2): or or . Let be defined as in by . Therefore labels of vertices are as follows:
The label assigned to the central vertex is given by
(i) | When , we have |
(ii) | When , we have |
(iii) | When , we have |
The label assigned to the central vertex is given by
(i) | When , we have |
(ii) | When , we have |
(iii) | When , we have |
Illustration: The edge odd graceful labeling of the double fan graphs and and are shown in .
13 Edge odd graceful labeling of polar grid graph
Theorem 12
The polar grid graph , with radius and radii is an edge odd graceful graph.
Proof
Here , and , there are two cases:
Case (1): When is even. Let the polar grid graph , be as in . First move clockwise to label the radii edges by , then move anticlockwise to label the radii edges by , then move clockwise to label the edges by , and so on. Finally move anticlockwise to label the edges: by .
Now move clockwise to label the edge cycles as follows: First label the edges of inner cycle by and label the edges of second cycle by and so on.
Then label the edges of the cycle of order , by , then label the edges of the cycle of order , by . Then label the edges of order , . By . Finally label the edges of the cycle of order , by Thus we have the labels of vertices are as follows: . Now the label assigned to central vertex is given by
Case (2): When is odd. There are two subcases
(i) | When . Let the polar grid graph , be as in . The label of radial edges is the same as when is even. Move anticlockwise to label the edges of inner cycle , by, the move the edges of second cycle by and so on. |
Finally label the edges of the cycle of order by . Thus we have the labels of vertices are as follows: .
Now the label assigned to central vertex is given by
(ii) | When and . The proof is very similar as in subcase (i), only we interchange the labels of two radii edges and to avoid repeated labels of vertices. In this case . |
Illustration : The edge odd graceful labelings of the polar grid graphs and are shown in .
Notes
Peer review under responsibility of Kalasalingam University.
References
- Bloom G.S. Golomb S.W. Applications of numbered undirected graphs Proc. IEEE 65(4) 1977 562 570
- Bloom G.S. Golomb S.W. Numbered complete graphs, unusual rulers and assorted applications Theory and Applications of Graphs Lecture Notes in Math vol. 642 (1978) Springer-Verlag. New York. 53–65.
- Sutton M. (Ph.D. thesis) Summable Graphs Labellings and their Applications 2001 Dept. Computer Science, The University of Newcastle
- Rosa A. On certain valuations of the vertices of a graph, Theory of graphs Internat. Symp, Rome, July 1966 1967 Gordan and Breach N.Y and Paris 349 355
- Golomb S.W. How to Number a Graph Read R.C. Graph Theory and Computing 1972 Academic Press New York 23 37
- Gnanajothi R.B. Ph.D. Thesis Topics in Graph Theory 1991 Madurai Kamaraj University
- Lo S.P. On edge-graceful1abelings of graphs Congr. Numer. 50 1985 231 241
- Solairaju A. Chithra K. Edge-odd graceful graphs Electron. Notes Discrete Math. 33 2009 15 20