Printer Friendly
The Free Library
22,695,004 articles and books

Strong edge graceful labeling of some graphs.

1. INTRODUCTION

All graphs in this paper are finite finite - compact , simple and undirected. Terms not defined here are used in the sense of Harary [1]. The symbols V(G) will denote de·note  
tr.v. de·not·ed, de·not·ing, de·notes
1. To mark; indicate: a frown that denoted increasing impatience.

2.
 the vertex A corner point of a triangle or other geometric image. Vertices is the plural form of this term. See vertex shader.  set and edge set of a graph G. The cardinality A quantity relationship between elements. For example, one-to-one, one-to-many and many-to-one express cardinality. See cardinal number.

(mathematics) cardinality - The number of elements in a set. If two sets have the same number of elements (i.e.
 of the vertex set is called the order of G. The cardinality of the edge set is called the size of G. A graph with p vertices The plural of vertex. See vertex.  and q edges is called a (p,q) graph.

Lo [3] introduced the notion of edge graceful grace·ful  
adj.
Showing grace of movement, form, or proportion: "Capoeira is a graceful ballet of power and control, artists kicking and jumping in synchronized movement" Alisa Valdes.
 graphs. A graph G with q edges and p vertices is said to be edge graceful if there exists a bijection f from the edge set to the set {1,2, ..., q} so that the induced induced /in·duced/ (in-dldbomacst´)
1. produced artificially.

2. produced by induction.

induced,
adj artificially caused to occur.


induced

induction.
 mapping [f.sup.+] from the vertex set to the set {0,1,2, ..., p-1} given by [f.sup.+](x) = [summation summation n. the final argument of an attorney at the close of a trial in which he/she attempts to convince the judge and/or jury of the virtues of the client's case. (See: closing argument) ]{f(xy)/xy [member of]E(G)} (mod p) is a bijection.

The necessary condition for a graph to be edge graceful is q(q+1) [equivalent to] 0 or p/2 (mod p). With this condition one can verify (1) To prove the correctness of data.

(2) In data entry operations, to compare the keystrokes of a second operator with the data entered by the first operator to ensure that the data were typed in accurately. See validate.
 that even cycles, and paths of even length are not edge graceful. But whether trees of odd order are edge graceful is still open. On these lines, we define a new type of labeling called strong edge graceful labeling In graph theory, a graceful labeling of a graph with n vertices and e edges is a labeling of its vertices with distinct integers between 0 and e inclusive, such that each edge is uniquely identified by the positive, or absolute difference between its  by relaxing its range through which we can get edge graceful labeling of odd order trees for some family of graphs.

A (p,q) graph G is said to have strong edge graceful labeling if there exists an injection f from the edge set to {1, 2, ..., [3q/2]} so that the induced mapping [f.sup.+] from the vertex set to {0,1, ..., 2 p-1} defined by [f.sup.+](x) = [summation]{f(xy)}/xy [member of]E(G)} (mod 2p) are distinct. A graph G is said to be strong edge graceful if it admits a strong edge graceful labeling. In this paper, we investigate strong edge graceful labeling (SEGL) of some graphs.

2. MAIN RESULTS

Theorem theorem, in mathematics and logic, statement in words or symbols that can be established by means of deductive logic; it differs from an axiom in that a proof is required for its acceptance.  2.1: [C.sub.n] is strong edge graceful for all n where n is odd and n [greater than or equal to] 3.

Proof: Let [v.sub.1], [v.sub.2], ..., [v.sub.n] be the vertices of [C.sub.n] and [e.sub.1], [e.sub.2], ..., [e.sub.n] be the edges of [C.sub.n] denoted as in fig.1

[FIGURE 1 OMITTED]

We first label the edges [C.sub.n] of as follows

f ([e.sub.i]) = i for i = 1 to n. Then the induced vertex labels are

[f.sup.+] ([v.sub.1]) = n+1; [f.sup.+] ([v.sub.i]) = 2i-1 for i = 1,2,3, ..., n

Clearly {[f.sup.+] ([v.sub.i]): i = 1 to n} are distinct. Hence, [C.sub.n] is strong edge graceful for all n odd and n [greater than or equal to] 3. The strong edge graceful labeling of [C.sub.7] and [C.sub.11] are given below.

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

Theorem 2.2: [C.sub.n] is strong edge graceful for all n where n is even and n [greater than or equal to] 4.

Proof: Let [v.sub.1], [v.sub.2], ..., [v.sub.n] be the vertices of [C.sub.n] and [e.sub.1], [e.sub.2], ..., [e.sub.n] be the edges of [C.sub.n] denoted as in fig. 1. We first label the edges of [C.sub.n] as follows

f([e.sub.i]) = i for i = 1 to n-1 ; f([e.sub.n]) = n+1. Then the induced vertex labels are

[f.sup.+] ([v.sub.1]) n + 2; [f.sup.+] ([v.sub.n]) = 0

[f.sup.+] ([v.sub.2]) = 3; [f.sup.+] ([v.sub.i]) = [f.sup.+] ([v.sub.i-1]) + 2 for i = 3 to n-1

Clearly {[f.sup.+] ([v.sub.i]: i = 1 to no} are distinct. Hence, [C.sub.n] is strong edge graceful for all n even and n [greater than or equal to] 4. The strong edge graceful labeling of [C.sub.6] and [C.sub.8] are illustrated in fig. 4 and fig.5 respectively.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Theorem 2.3: [P.sub.n] is strong edge graceful for all n odd and n [greater than or equal to] 3.

Proof: Let [v.sub.1], [v.sub.2], ..., [v.sub.n] be the vertices of [P.sub.n] and {[e.sub.1], [e.sub.2], ..., [e.sub.n-1] be the edges of [P.sub.n] as defined in the fig. 6.

[FIGURE 6 OMITTED]

We first label the edges of [P.sub.n] as f([e.sub.i]) = i for i = 1 to n-1 Then the induced vertex labels are [f.sup.+] ([v.sub.1]) = 1; [f.sup.1] ([v.sub.1]) = 2i-1 for i = 2 to n-1.; [f.sup.+] ([v.sub.n]) = n-1

Clearly {[f.sub.+]([v.sub.i]): i = 1 to n} are all distinct. Hence [P.sub.n] is strong edge graceful for all n odd and n [greater than or equal to] 3. The strong edge graceful labeling of [P.sub.9] and [P.sub.13] are illustrated fig. 7 and fig. 8 respectively.

[FIGURE 7 OMITTED]

[FIGURE 8 OMITTED]

Theorem 2.4: [P.sub.n] is strong edge graceful for all n even and n [greater than or equal to] 4.

Proof: Let [v.sub.1], [v.sub.2] ..., [v.sub.n] be the vertices of [P.sub.n] and {[e.sub.1], [e.sub.2], ..., [e.sub.n-1]} be the edges of [P.sub.n] as defined in the fig. 6. We first label the edges of [P.sub.n] as follows:

f ([e.sub.i]) = i for i = 1 to n - 2; f([e.sub.n-1]) = n Then the induced vertex labels are

[f.sup.+] ([v.sub.i]) = 2i - 1 for i = 1 to n-2.; [f.sup.+] ([v.sub.n-i]) = 2n-2; [f.sup.+] ([v.sub.n]) = n. Clearly

{[f.sup.+] ([v.sub.i]): i = 1 to n} are all distinct. Hence [P.sub.n] is strong edge graceful for all n even and n [greater than or equal to] 4. The strong edge graceful labeling of [P.sub.6] and [P.sub.8] are illustrated fig. 9 and fig. 10 respectively.

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

Theorem 2.5: [C.sup.+.sub.n] is strong edge graceful for all n [greater than or equal to] 3.

Proof: Let {[v.sub.1], [v.sub.2] ..., [v.sub.n]} [union] {[v'.sub.1], [v'.sub.2] ..., [v'.sub.n]} be the vertices of [C.sup.+.sub.n]. The edges of [C.sup.+.sub.n] are {[e.sub.i] = [v.sub.i] [v.sub.i+1]: i = 1 to n - 1} [union] {[e.sub.n] = [v.sub.n] [v.sub.1]} [union] {[v.sub.i] [v'.sub.i]: i = 1 to n} are denoted as in fig.11

[FIGURE 11 OMITTED]

We first label the edges of [C.sup.+.sub.n] as follows: f([e.sub.i]) = i for i = 1 to n; f([v.sub.i] [v'.sub.i]) = 2n- i+1 for i = 1 to n

Then the induced vertex labels are

[f.sup.+]([v.sub.i]) = 2n + 1 + i for i = 1 to n. ; [f.sup.+]([v'.sub.i]) = 2n + 1 - i for i = 1 to n.

Clearly {[f.sup.+]([v.sub.i]), [f.sup.+]([v'.sub.i])} are distinct. Hence, [C.sup.+.sub.n] is strong edge graceful for all n [greater than or equal to] 3.

The labeling of [C.sup.+.sub.7] are [C.sup.+.sub.8] illustrated in fig. 12 and fig. 13 respectively.

[FIGURE 12 OMITTED]

[FIGURE 13 OMITTED]

Theorem 2.6: [K.sub.1,2n] is strong edge graceful for all n [greater than or equal to] 1.

Proof: Let {v, [v.sub.1], [v.sub.2], ..., [v.sub.2n]} be the vertices of [K.sub.1,2n] and {[e.sub.1], [e.sub.2], [e.sub.3], ..., [e.sub.2n]} be the edges of [K.sub.1,2n] denoted as in fig. 14.

[FIGURE 14 OMITTED]

We first label the edges of [K.sub.1,2n] as f([e.sub.i]) = i for i = 1, 2, ..., 2n. Then the induced vertex labels are [f.sup.+]([v.sub.i]) = i for i = 1, 2, ..., 2n

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE re·pro·duce  
v. re·pro·duced, re·pro·duc·ing, re·pro·duc·es

v.tr.
1. To produce a counterpart, image, or copy of.

2. Biology To generate (offspring) by sexual or asexual means.
 IN ASCII ASCII or American Standard Code for Information Interchange, a set of codes used to represent letters, numbers, a few symbols, and control characters. Originally designed for teletype operations, it has found wide application in computers. ]

Then the induced vertex labels are all distinct. Hence, [K.sub.1,2n] is strong edge graceful for all n [greater than or equal to] 1. The strong edge graceful labeling of [K.sub.1,6] and [K.sub.1,8] are illustrated in fig.15 and fig 16 respectively.

[FIGURE 15 OMITTED]

[FIGURE 16 OMITTED]

Theorem 2.7: [K.sub.1,4n-1] is strong edge graceful for all n [greater than or equal to] 1.

Proof: Let {v, [v.sub.1], [v.sub.2], ..., [v.sub.4n-1]} be the vertices of [K.sub.1,4n-1] and {[e.sub.1], [e.sub.2], [e.sub.3], ..., [e.sub.4n-1]} be the edges of denoted as in fig.14. We first label the edges of [K.sub.1,4n-1] as follows f([e.sub.i]) = i for i = 1, 2, ..., 4n-1. Then the induced vertex labels are [f.sup.+]([v.sub.i]) = i for i = 1, 2, ..., 4n-1; [f.sup.+](v) = 6n. Then the induced vertex labels are all distinct. Hence, [K.sub.1,4n-1] is strong edge graceful for all n [greater than or equal to] 1. The strong edge graceful labeling of [K.sub.1,7] and [K.sub.1,11] are illustrated in fig.17 and fig 18 respectively.

[FIGURE 17 OMITTED]

[FIGURE 18 OMITTED]

Theorem 2.8: [K.sub.1,4n-1] is strong edge graceful for all n [greater than or equal to] 1.

Proof: Let {v, [v.sub.1], [v.sub.2], ..., [v.sub.4n-1]} be the vertices of [K.sub.1,4n-1] and {[e.sub.1], [e.sub.2], [e.sub.3], ..., [e.sub.4n-1]} be the edges of [K.sub.1,4n-1] denoted as in fig.14. We first label the edges of as follows f([e.sub.i]) = i for i = 1, 2, ..., 4n ; f([e.sub.4n+1]) = [3q/2] Then the induced vertex labels are [f.sup.+]([v.sub.i]) = i for i = 1, 2, ..., 4n - 1 ; [f.sup.+]([v.sub.4n+1]) = [3q/2] ; [f.sup.+](v) = 4n + 1 Then the induced vertex labels are all distinct. Hence, [K.sub.1,4n-1] is strong edge graceful for all n [greater than or equal to] 1. The strong edge graceful labeling of [K.sub.1,5] and [K.sub.1,9] are illustrated in fig.19 and fig. 20 respectively.

[FIGURE 19 OMITTED]

[FIGURE 20 OMITTED]

Definition 2.1: Let [P.sub.n] denote the path with n vertices. Then the join of [K.sub.1] with [P.sub.n] is defined as fan and is denoted by [F.sub.n] i.e. [F.sub.n] = [K.sub.1] + [P.sub.n].

Theorem 2.9: [F.sub.4n-2] is strong edge graceful graph for all n [greater than or equal to] 1.

Proof : Let {v, [v.sub.1], [v.sub.2], [v.sub.3], ..., [v.sub.4n-2]} be the vertices of [F.sub.4n-2] and the edges of [F.sub.4n-2] are defined as follows as denoted in fig. 21.

[FIGURE 21 OMITTED]

We first label the edges of [F.sub.4n-2] as follows: f([e.sub.i]) = i for i = 1 to 4n - 3, f(v[v.sub.i]) = 2n - i for i = 1 to 4n - 2 then the induced vertex labels are [f.sup.+]([v.sub.1]) = 2(4n - 2); [f.sup.+]([v.sub.i]) = f([v.sub.i-1]) + 1 for i = 2 to 4n - 1.; [f.sup.+]([v.sub.n-2]) = 8n - 5; [f.sup.+](v) = 4n + 1

The labeling of [K.sub.6], [K.sub.10] are illustrated in fig.22 and fig.23 respectively.

[FIGURE 22 OMITTED]

[FIGURE 23 OMITTED]

Theorem 2.10: [F.sub.4n+1] is strong edge graceful graph for all n [greater than or equal to] 1.

Proof Let {v, [v.sub.1], [v.sub.2], [v.sub.3], ..., [v.sub.4n+1]} be the vertices of [F.sub.4n+1] and the edges of [F.sub.4n+1] are defined as follows {v[v.sub.i]: i = 1 to 4n + 1}[union] {[e.sub.i] = ([v.sub.i],[v.sub.i+1]): i = 1 to 4n} as denoted in fig21. We first label the edges of [F.sub.4n+1] as follows: f([v.sub.i]) = i for i = 1 to 4n; f(v[v.sub.1]) = (4n + 1) f(v[v.sub.i]) = p (4n + 1) - i for i = 2 to (4n + 1) then the induced vertex labels are [f.sup.+]([v.sub.1]) = 4n + 2 ; [f.sup.+]([v.sub.i]) = n - 2 for i = 2 to 4n. [f.sup.+]([v.sub.4n+1]) = 2n ; [f.sup.+](v) = 3n + 7/2

The labeling of [F.sub.5] are illustrated in fig.24..

[FIGURE 24 OMITTED]

REFERENCES

[1.] Harary, F. 1972. Graph Theory graph theory

Mathematical theory of networks. A graph consists of vertices (also called points or nodes) and edges (lines) connecting certain pairs of vertices. An edge that connects a node to itself is called a loop.
. Addison Addison, village (1990 pop. 32,058), Du Page co., NE Ill.; inc. 1884. An industrial suburb of Chicago, it manufactures machinery and plastic items.  Wesley, Mass Reading (1972).

[2.] Joseph, A. Gallian. 2007.A Dynamic Survey of Graph Labeling In the mathematical discipline of graph theory, a graph labeling is the assignment of integers to the edges or vertices, or both, of a graph. The labeling strategy depends on the category of the labeling. Definition
Given a graph
. The Electronic journal of combinatorics combinatorics (kŏm'bənətôr`ĭks) or combinatorial analysis (kŏm'bĭnətôr`ēəl)  14(2007)#DS6.

[3.] Lo, S. 1985. On edge graceful labeling of graphs, Congressus numerantium 50(1985).

[4.] Slamet, S. and Sugeng, K.A. 2008. Sharing scheme using magic covering--Preprint. 2008.

B. Gayathri * and M. Subbiah@

PG and Research Dept. of Mathematics, Periyar E.V.R. College, Trichy--23, India Email; maduraigayathri@gmail.com, mdthrcp@gmail.com
COPYRIGHT 2008 A.K. Sharma, Ed & Pub
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

 Reader Opinion

Title:

Comment:



 

Article Details
Printer friendly Cite/link Email Feedback
Author:Gayathri, B.; Subbiah, M.
Publication:Bulletin of Pure & Applied Sciences-Mathematics
Article Type:Report
Geographic Code:9INDI
Date:Jan 1, 2008
Words:2263
Next Article:On B- Covering dimension of fuzzy bitopological spaces.
Topics:

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters