Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

One Modulo Three Mean Labeling of Graphs

P. Jeyanthi*, A. Maheswari

Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur, Tamilnadu, India

Abstract: In this paper, we introduce a new labeling called one modulo three mean labeling. A graph G is said to be one modulo three mean graph if there is an injective function from the vertex set of G to the set {a | 0 ≤ a ≤ 3q-2 and either a≡0(mod 3) or a≡1(mod 3) } where q is the number of edges of G and induces a bijection from the edge set of G to given by and the function is called one modulo three mean labeling of G. Furthermore, we prove that some standard graphs are one modulo three mean graphs.

Keywords: one modulo three mean labeling, one modulo three mean graph

Received July 31, 2014; Revised August 25, 2014; Accepted August 28, 2014

Citation: P. Jeyanthi, A. Maheswari, One Modulo Three Mean Labeling of Graphs. American Journal of Applied Mathematics and Statistics, 2 (5). 302-306. January 2014. doi:10.12691/ajams-2-5-2

1. Introduction and Definitions

All graphs considered here are simple, finite, connected and undirected. We follow the basic notations and terminologies of graph theory as in [1].Given a graph G, the symbols V (G) and E (G) denote the vertex set and the edge set of the graph G, respectively. Let G= G(p, q) be a graph with p = |V(G)| vertices and q = |E(G)| edges. A graph labeling is an assignment of integers to the vertices or edges or both, subject to certain conditions. There are several types of graph labeling and a detailed survey is available in [2].

V. Swaminathan and C.Sekar introduced the concept of one modulo three graceful labeling in [5]. S.Somasundram and R.Ponraj introduced mean labeling of graphs in [3] and further studied in [4]. Motivated by the work of these authors we introduce a new type of labeling known as one modulo three mean labeling and prove that some standard graphs are one modulo three mean graphs. We use the following definitions in the subsequent sections.

Definition 1.1: A comb graph is a graph obtained by joining a single pendant edge (vertex with degree one) to each vertex of a path.

Definition 1.2: A caterpillar is a tree with the property that the removal of its end vertices (vertices with degree one) leaves a path.

Definition 1.3: Bistar Bm,n is a graph obtained from K₂ by joining m pendant edges to one end of K₂ and n pendant edges to the other end of K₂. The edge of K2 is called the central edge of Bm,n and the vertices of K₂ are called the central vertices of Bm,n.

Definition 1.4: Let T be a tree with at least four vertices. Let u₀ and v₀ be the two adjacent vertices of T and let u and v be the leaves of T with the property that the length of the u₀-u path is equal to the length of v₀-v path. If the edge u₀v₀ is deleted from T and u and v are joined by an edge uv, then such a transformation of T is called an elementary parallel transformation (or an ept) and the edge u₀v₀ is called transformable edge. If by applying a sequence of ept’s, T can be reduced to a path, then T is called a Tp-tree (transformed tree) and such a sequence regarded as a composition of mappings (ept’s) denoted by P, is called a parallel transformation of T. The path, the image of T under P is denoted as P(T).

For any integer n, denotes the smallest integer not less than n.

2. One Modulo Three Mean Labeling

Definition 2.1: A graph G is said to be one modulo three mean graph if there is an injective function from the vertex set of G to the set {a | 0 ≤ a ≤ 3q-2 and either a ≡ 0(mod 3) or a ≡ 1(mod 3) } where q is the number of edges of G and induces a bijection from the edge set of G to {a | 1 ≤ a ≤ 3q-2 and a ≡ 1(mod 3) }given by *(uv) = and the function is called one modulo three mean labeling of G.

Remark: If G is a one modulo three mean graph with more than two edges then 0, 1, 3(q-1) and 3q-2 must be the vertex labels.

Theorem 2.2: Let G be a one modulo three mean graph with one modulo three mean labeling . Let t be the number of edges whose one vertex label is even and the other label is odd then where d (v) denotes the degree of a vertex v.

Proof: Since is one modulo three mean labeling of G, we have *(xy) = .

Now = = q(3q-1)-t.

Hence, .

As an illustration, we consider the cycle graph C₅=

Define : V (C₅)→ by () = 0, () = 1, () = 7, ()=12, () = 13. Clearly is one modulo three mean labeling. Here t=4.

Now

Theorem 2.3: Let G be a one modulo three mean graph containing a cycle C₃=uvwu. If is an one modulo three mean labeling of G then and for any x,y.

Proof: Suppose . Assume = 3x+1, =3x+6y+1, =3x+6y then the edges u v and u w get the same label 3x+3y+1 which is not possible.

Suppose. Assume =3x, =3x+1, =3x+6y+1 then the edges u w and v w get the same label 3x+3y+1 which is not possible.

Theorem 2.4: Let G be a one modulo three mean graph then (i) 3x and 3x+4 cannot be the labels of the adjacent vertices and (ii) 3x+1 and 3(x+1) cannot be the labels of the adjacent vertices (iii) 3x and 3y cannot be the labels of the adjacent vertices and (iv) 3x+1 and 3x+4 cannot be the labels of adjacent vertices.

Proof: (i) Suppose that uv is an edge of G with =3x and =3x+4 then the induced edge label of uv is 3x+2. This is a contradiction to the fact that the edge labels are congruent to one modulo three. Therefore, 3x and 3x+4 cannot be the labels of the adjacent vertices.

(ii) Suppose that uv is an edge of G with =3x+1 and =3x+3 then the induced edge label of uv is 3x+2. This is a contradiction to the fact that the edge labels are congruent to one modulo three. Therefore, 3x+1 and 3(x+1) cannot be the labels of the adjacent vertices.

On the same line, we can prove (iii) and (iv).

3. One Modulo Three Mean Labeling of Some Trees

Theorem 3.1: The path Pn is a one modulo three mean graph if n is even.

Proof: Let V (Pn) = and E(Pn)= . Define the vertex labeling : V (Pn)→ by () = 6(i-1), 1≤ i ≤ and () = 6(i-1)+1, 1≤ i ≤ , then the induced edge labels are . Hence is a one modulo three mean labeling of Pn. Therefore, Pn(n is even) is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph P₈ is given in Figure1.

Figure 1.

Theorem 3.2: The star graph K1, n is a one modulo three mean graph if and only if n = 1.

Proof: If n = 1, the star graph K1,1 is a path P₂. Hence K1,1 is a one modulo three mean graph.

Conversely assume that n ≥ 2. Suppose K1, n is a one modulo three mean graph with one modulo three mean labeling . Let (V₁, V₂) be the bipartition of K1, n with V₁= and V₂=. To get the edge label 1, we must have 0 and 1 as the labels of the adjacent vertices. Therefore, either (u)=0 or (u)=1. In both the cases there is no edge with the label 3n-2. This contradiction proves that K1,n is not a one modulo three mean graph for n ≥ 2.

Theorem 3.3: The caterpillar G obtained by attaching n pendant edges to each vertex of the path Pm is a one modulo three mean graph if m≡0(mod2).

Proof: Let G be a caterpillar obtained from the path Pm = by attaching n pendant edges to each of its vertices. Let uij, 1≤ j ≤ n be the vertices attached to the vertex ui, 1≤ i ≤ m of Pm then G is isomorphic to Pm nK₁ and it has m(n+1) vertices and m(n+1)-1 edges.

Define : V (G)→ as follows: For 1≤ i ≤ m, 1≤ j ≤ n

then the induced edge labels are . Hence, is one modulo three mean labeling. Therefore, the caterpillar G obtained by attaching n pendant edges to each vertex of the path Pm is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph P₄ is given in Figure 2.

Figure 2.

Corollary 3.4: The comb graph and the Bistar Bn,n are one modulo three mean graphs.

Theorem 3.5: The bistar Bm,n, is a one modulo three mean graph if and only if m = n.

Proof: If m = n, by Corollary 3.4 Bm,n is a one modulo three mean graph. Conversely assume that Bm,n is a one modulo three mean graph with m ≠ n. Without loss of generality, assume that m > n. Let the vertex set V(Bm,n) =and the edge set E(Bm,n) =. Clearly Bm,n has m+n+2 vertices and q = m+n+1 edges. Let be the one modulo three mean labeling of Bm,n.

First, we prove that 3q-2 and 3q-3. Suppose that either 3q-2 or 3q-3. 3q-2 = 3m+3n+1 > 6n+1. Therefore, > 3n+1 and > 3n. Hence, the labels of the edges and uv are greater than 3n+1. But the set contains only m elements, whereas the edges and uv are m+1 in number. Hence, 3q-2 and 3q-3.

Next, we prove that 3q-2 and 3q-3. Suppose that either 3q-2 or 3q-3. Since q > 2 there is an edge with label 1. Hence, either = 0 or = 0 for some i.

If = 0 then the labels of the edges , uv are less than or equal to . Since m > n, m+1 > . Therefore, the number of elements in the set is less than m+1whereas the edges and uv are m+1 in number. Hence, 3q-2 and 3q-3.

If =0 for some i then must be 1. Hence, the labels of the edges and uv are less than or equal to . But the number of elements in the set is less than m+1 whereas the edges and uv are m+1 in number. Hence, 3q- 2 and 3q-3.

Also 3q-2 or 3q-3 cannot be the label for any of the vertices since otherwise 3q-2 or 3q-3 will be the label for u. Similarly 3q-2 or 3q-3 cannot be the label for any of the vertices . Therefore, 3q-2 is not a label for any vertex. Hence, Bm,n, m > n is not a one modulo three mean graph.

Theorem 3.6: A Tp-tree with even number of vertices is a one modulo three mean graph.

Proof: Let T be a Tp-tree with |V(T)| = n where n is even. By the definition of a transformed tree there exists parallel transformation P of T such that P(T) is a path. For the path P(T) we have (i)V(P(T)) = V(T) (ii)E(P(T)) = (E(T) \ Ed) ∪ Ep where Ed is the set of edges deleted from T and Ep is the set of edges newly added through the sequence P = (P₁, P₂,..., Pk) of the epts P used to arrive the path P(T). Clearly Ed and Ep have the same number of edges. Denote the vertices of P(T) successively as v₁,v₂,…,vn starting from one pendant vertex of P(T) right up to the other.

Define : V(P(T)) → by

for 1 ≤ i ≤ n. Clearly is one modulo three mean labeling of the path P(T).

Let vivj be an edge of T for some indices i and j, 1 ≤ i ≤ n and let P₁ be the ept that deletes this edge and adds the edge vi+tvj-t where t is the distance from vi to vi+t and also the distance from vj to vj-t. Let P be a parallel transformation of T that contains P₁ as one of the constituent epts. Since vi+tvj-t is an edge of the path P(T), it follows that i + t + 1 = j - t which implies j = i + 2t +1. The induced label of the edge vivj is given by,

Hence, we have*(vivj)= *(vi+tvj-t) and therefore is one modulo three mean labeling of the Tp -tree T.

An example for one modulo three mean labeling of a Tp-tree with 18 vertices is given in Figure 3.

Figure 3.

4. One Modulo Three Mean Labeling of Cycle Related Graphs

In this section, we prove that some cycle related graphs are one modulo three mean graphs.

Theorem 4.1: Cycle Cn is a one modulo three mean graph if n≡1(mod4).

Proof: Let n = 4k+1. Let v₁, v2 ,…, vn be the vertices of Cn.

Define : V(Cn)→ by

The induced edge labels of the cycle Cn are . Hence, Cn is a one modulo three mean graph if n≡1(mod4).

An example for one modulo three mean labeling of the graph C13 is given in Figure4.

Figure 4.

Theorem 4.2: The ladder graph Ln =Pn×P₂ is a one modulo three mean graph if n is odd.

Proof: Let the vertex set of Ln be and the edge set of Ln be . Clearly Ln has 2n vertices and 3n-2 edges.

Define : V( Cn )→ by (u₁)=0, (un)=9(n-1), (u2i)=18i-11

if 1 ≤ i ≤, (u2i+1)=18i+6 if 1 ≤ i ≤-1 and (v₁)=1, (vn)=9n - 8, (v2i)=6(3i-1)

if 1 ≤ i ≤ ,(v2i+1)=18i-5 if 1 ≤ i ≤-1. Hence, the induced edge labels of Ln are then is one modulo three mean labeling. Hence, Ln is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph L₇ is given in Figure 5.

Figure 5.

If G₁ and G₂ are two graphs then G₁ G₂ is the Cartesian product of [1] G₁ and G₂.

Theorem 4.3: The graph K1,n K₂ is a one modulo three mean graph if n is even

Proof: Let the vertices of K1,n K₂ be and edges are .Clearly K1,n K₂ has 2n+2 vertices and 3n+1 edges. Define : V(K1,n K₂ )→ by (u)=0, (v)=9n+1, (un+1-i)=12i - 5 if 1 ≤ i ≤ , (ui)=12i - 11 if 1 ≤ i ≤ and (vn+1-i)=9n - 6(i-1) if 1 ≤ i ≤ , (vi)=6n - 6(i-1) if 1 ≤ i ≤ . The induced edge labels of K1,n K₂ are then is one modulo three mean labeling. Hence, K1,n K₂ is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph K1,₄ K₂ is given in Figure 6.

Figure 6.

Theorem 4.4: The complete graph Kn is a one modulo three mean graph if and only if n ≤ 2.

Proof: Suppose Kn is a one modulo three mean graph. To get the edge label 3q-2, we must have 3q-2 and 3q-3 as the vertex labels. Let u and v be the vertices whose labels are 3q-2 and 3q-3 respectively. Again, to get the edge label 1, we must have 0 and 1 as the vertex labels. Let w and z be the vertices whose labels are 0 and 1 respectively then the edges uw, vz receive the same induced label which should not happen. Hence Kn is not a one modulo three mean graph for n >3. If n = 2, the complete graph K₂ is a path P₂, which is a one modulo three mean graph.

References

[1]   | F.Harary, Graph theory, Addison Wesley, Massachusetts, (1972).
[2]   | J. A. Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics, DS6, 2013.
[3]   | S. Somasundaram and R. Ponraj, Mean Labeling of graphs, National Academy Science Letters Vol: 26,(2003), 210-213.
[4]   | S. Somasundaram and R. Ponraj, Some results on Mean graphs, Pure and Applied Mathematika Sciences, Vol: 58 (2003), 29-35.
[5]   | V. Swaminathan and C. Sekar, Modulo three graceful graphs, Proceed. National Conference on Mathematical and Computational Models, PSG College of Technology, Coimbatore, 2001, 281-286.