New Families of Mean Graphs

Let G(V, E) be a graph with p vertices and q edges. A vertex labeling of G is an assignment f : V(G) [arrow right] 1, 2, 3, . . . , p + q} be an injection. For a vertex labeling f, the induced Smarandachely edge m-labeling f*^sub S^ for an edge e = uv, an integer m ≥ 2 is defined by. ... Then f is called a Smarandachely super m-mean labeling if f(V(G)) ∪ f*(e) : e ∈ E(G)} = 1, 2, 3, . . . , p + q}. Particularly, in the case of m = 2, we know that. ... Such a labeling is usually called a super mean labeling. A graph that admits a Smarandachely super mean m-labeling is called Smarandachely super m-mean graph, particularly, super mean graph if m = 2. In this paper, we discuss two kinds of constructing larger mean graphs. Here we prove that (P^sub m^; C^sub n^)m ≥ 1, n ≥ 3, (P^sub m^; Q^sub 3^)m ≥ 1, (P^sub 2n^; S^sub m^)m ≥ 3, n ≥ 1 and for any n ≥ 1 (P^sub n^; S^sub 1^), (P^sub n^; S^sub 2^) are mean graphs. Also we establish that [P^sub m^; C^sub n^]m ≥ 1, n ≥ 3, [P^sub m^; Q^sub 3^]m ≥ 1 and [P^sub m^; C^sub n^^sup (2)^]m ≥ 1, n ≥ 3 are mean graphs. Key Words: Labeling, mean labeling, mean graphs, Smarandachely edge m-labeling, Smarandachely super m-mean labeling, super mean graph. AMS(2000): 05C78.






Publication: International Journal of Mathematical Combinatorics
Author: Avadayappan, Selvam
Date published: July 1, 2010

(ProQuest: ... denotes formulae omitted.)

1 . Introduction

Throughout this paper, by a graph we mean a finite, undirected, simple graph. Let G(V: E) be a graph with ? vertices and q edges. A path on ? vertices is denoted by Pn and a cycle on ? vertices is denoted by Cn. The graph P^sub 2^ P^sub 2^ P^sub 2^ is called the cube and is denoted by Q%. For notations and terminology we follow [I].

A vertex labeling of G is an assignment / : V(G) [arrow right] 1, 2, 3, . . . ,p + q} be an injection. For a vertex labeling /, the induced Smarandachely edge m- labeling /g for an edge e = uv: an integer m ≥ 2 is denned by

...

Then f is called a Smarandachely super rn-mean labeling if /(V(G)) ∪ f*(e) : e G E (G)} l, 2, 3, ... ,p -h q}. Particularly, in the case of m = 2, we know that

...

Such a labeling is usually called a super mean labeling. A graph that admits a Smarandachely super mean m-labeling is called Smarandachely super rn-mean graph^ particularly, super mean graph if m = 2. The mean labeling of the Petersen graph is given in Figure 1.

A super mean labeling of the graph K^sub 2,4^ is shown in Figure 2.

The concept of mean labeling was first introduced by Somasundaram and Ponraj [2] in the year 2003. They have studied in [2-5,8-9], the meanness of many standard graphs like P^sub n^, C^sub n^, K^sub n^(n < 3), the ladder, the triangular snake, K^sub 1,2^, K^sub 1,3^, K^sub 2,n^, K^sub 2^+mK^sub 1^ K^sup c^^sub n^+2K^sub 2^: S^sub m^ + K^sub 1^, C^sub m^ ∪ P^sub n^(m ≥ 3, n ≥ 2), quadrilateral snake, comb, bistars B(n), B^sub n+1;n^, B^sub n+2,n^, tne carona of ladder, subdivision of central edge of B^sub n,n^, subdivision of the star K^sub 1,n^(n ≤ 4), the friendship graph C^sup (2)^^sub 3^, crown C^sub n^ K^sub 1^ C^sup (2)^^sub n^, the dragon, arbitrary super subdivision of a path etc. In addition, they have proved that the graphs K^sub n^(n > 3), K^sub 1,n^(n > 3), B^sub mjn^(m > n + 2), S(K^sub 1,n^)n > 4, C^sup (t)^^sub 3^ (t > 2), the wheel Wn are not mean graphs.

The concept of super mean labeling was first introduced by R. Ponraj and D. Ramya [6]. They have studied in [6-7] the super mean labeling of some standard graphs. Also they determined all super mean graph of order < 5. In [10], the super meanness of the graph C^sub 2n^ for n ≥ 3, the if-graph, Corona of a if-graph, 2-corona of a if-graph, corona of cycle C^sub n^ for n ≥ 3, m(7n-snake for m > l, n > 3 and n ^ 4, the dragon Pn(C7n) for m ≥ 3 and m ^ 4 and C^sub m^ x Pn for m = 3, 5 are proved.

Let Cn be a cycle with fixed vertex v and (P7n; Cn) the graph obtained from m copies of Cn and the path P^sub m^ : u^sub 1^u^sub 2^ . . . um by joining HI with the vertex v of the ith copy of Cn by means of an edge, for 1 ≤ i ≤ m.

Let Qs be a cube with fixed vertex v and (P7n; Qs) the graph obtained from m copies of Qs and the path P^sub m^ : u^sub 1^u^sub 2^ . . . um by joining HI with the vertex v of the ith copy of Qs by means of an edge, for 1 < i < m.

Let S^sub m^ be a star with vertices v^sub 0^ v^sub 1^ v^sub 2^, . . . , v^sub m^. Define (Pin] Sm) to be the graph obtained from 2n copies of Sm and the path P^sub 2n^ : u^sub 1^u^sub 2^ . . .v^sub 2n^ by joining Uj with the vertex VQ of the jth copy of S^sub m^ by means of an edge, for 1 < j < 2n, (Pn; Si) the graph obtained from n copies of Si and the path P^sub n^ : u^sub 1^u^sub 2^ . . . un by joining Uj with the vertex v^sub 0^ of the jth copy of S^sub 1^ by means of an edge, for 1 ≤ j ≤ n, (P^sub n^; S^sub 2^) the graph obtained from n copies of S^sub 2^ and the path P^sub n^ : u^sub 1^u^sub 2^ . . .un by joining Uj with the vertex VQ of the jth copy of S^ by means of an edge, for 1 < j < n.

Suppose C^sub n^ : v^sub 1^v^sub 2^ . . . v^sub n^v^sub 1^ be a cycle of length n. Let [P7n; Cn] be the graph obtained from m copies OfCn with vertices v^sub 1^v^sub 2^, . . . ,V^sub in^, v^sub 2l^, . . . , v^sub 2n^, . . . , v^sub mi^, . . .,V^sub m^n and joining v^sub ij^ and v^sub 1^+1^sub j^ by means of an edge, for some j and 1 < i < m - 1.

Let Q^sub 3^ be a cube and [P^sub m^; Q^sub 3^] the graph obtained from m copies of Qs with vertices ....

Let C^sup (2)^^sub n^ be a friendship graph. Define [P^sub m^; C^sup (2)^^sub n^}] to be the graph obtained from m copies of Cn and the path P^sub m^ : u^sub 1^u^sub 2^ . . .u^sub m^ by joining u^sub i^ with the center vertex of the ith copy of C^sup (2)^^sub n^ for 1 < i < m.

In this paper, we prove that ... are mean graphs.

2. Mean Graphs (P^sub m^; G)

Let t? be a graph with fixed vertex v and let (P^sub m^; G) be the graph obtained from m copies of t? and the path P^sub m^ : u^sub 1^u^sub 2^ . . . um by joining Ui with the vertex ? of the i/l copy of G by means of an edge, for 1 < i < m.

For example (P^sub 4^ 6^sub 4^) is shown in Figure 3.

Theorem 2.1 (Pm; Cn) is a mean graph, n ≥ 3.

Proof Let ... be the vertices of Pm. Then define / on V(Pm] Cn) as follows:

...

...

Label the vertices of v*. as follows:

Case (i) n is odd

When i is odd.

....

When i is even.

...

Case (ii) n is even

When i is odd.

...

When i is even,

...

The label of the edge ....

The label of the edge ...

and the label of the edges of the cycle are

....

For example, the mean labelings of (P6, C5) and (P5; C6) are shown in Figure 4,

Theorem 2.2 (Pm;Q3) is a mean graph.

Proof For 1 ≤ j ≤ 8, let v^sub i^sub j^^. be the vertices in the ith copy of Q3, 1 ≤ i ≤ m and u1, u2, .... m be the vertices of Pm.

Then define f on V(P^sub m^;Q^sub 3^) as follows:

....

When i is odd.

...

when i is even.

...

The label of the edges of Pm are 14i, 1 ≤ i ≤ m - 1.

The label of the edges of ...

The label of the edges of the cube are

14i - 1, 14i - 2, . . . , 14i - 12 if i is odd,

14i - 2, 14i - 3, . . . , 14i - 13 if i is even.

For example, the mean labeling of (P5,Q3) is shown in Figure 5,

Theorem 2.3 (P^sub 2n^; Sm) is a mean graph, m ≥ 3, n ≥ 1.

Proof Let .... be the vertices in the jth copy of S^sub m^, 1 ≤ j ≤ 2n.

Label the vertices of (P^sub 2n^; S^sub m^) as follows:

f(u^sub 2j^ + l (2m + 4)j, 0 ≤ j ≤ n - 1,

f(u^sub 2j^) (2m + 4)j - 1, 1 ≤ j ≤ n,

f(v^sub 0^sub 2j+1^^) (2m + 4)j + 1, 0 ≤ j ≤ n - 1,

f(v^sub 0^sub 2j^^) (2m + 4)j - 2, 1 ≤ j ≤ n,

f(v^sub i^sub 2j+1^^) + 1 (2m + 4)j + 2i, 0 ≤ j ≤ n - 1, 1 ≤ i ≤ m

f(v^sub i^sub 2j^^) - (2m + 4)(j - 1) + 2i + 1, 1 ≤ j ≤ n, 1 ≤ i ≤ m

The label of the edge u^sub j^u^sub j+1^ is (m + 2)j, 1 ≤ j ≤ 2n - 1

The label of the edge u^sub j^v^sub 0^sup j^^ is

...

The label of he edge v^sub 0^sub j^^ v^sub i^sub j^^ is

...

For example, the mean labeling of (P^sub 6^; S^sub 5^) is shown in Figure 6.

Theorem 2.4 (P^sub n^; S^sub 1^) and (P^sub n^; S^sub 2^) are mean graphs for any n ≥ 1.

Proof Let u^sub 1^,u^sub 2^, . . . ,u^sub n^ be the vertices of P^sub n^. Let v^sub o^sub 1^^, v^sub 0^sub 2^^, . . . , v^sub 0^sub n^ and v^sub 1^sub 1^^, v^sup 1^sub 2^^, . . . , v^sub 1^sub n^^ be the vertices of S^sub 1^.

Label the vertices of (P^sub n^; S^sub 1^) as follows:

...

The label of the edges of P^sub n^ are 3j, 1 < j < n - I.

The label of the edges ...

The label of the edges ...

Let ... be the vertices of S^sub 2^ Label the vertices of (P^sub n^] S^sub 2^] as follows:

...

...

...

...

The label of the edges of ...

The label of the edges ...

The label of the edges ...

The label of the edges ...

For example, the mean labelings of (Pr; 5i) and (Pe; 2) are shown in Figure 7,

3. Mean Graphs [P^sub m^;G]

Let G be a graph with fixed vertex v and let [P^sub m^; G] be the graph obtained from m copies of G by joining V^sub i^. and V^sub i^+-L. by means of an edge, for some j and 1 < i < m - 1.

For example [P^sub 5^] C^sub S^] is shown in Figure 8.

Theorem 3.1 [Pm] Cn] is a mean graph.

Proof Let ... be the vertices of the ith copy of C^sub n^, 1 ≤ i ≤ m and joining v^sub i^sub j^^(= u^sub i^) and v^sub i^+1.(= wst;+i) by means of an edge, for some j.

Case (i) ? = 4?,? = 1,2,3, ...

Define ... by

...

The label of the edge ^(t+1)^+i(t+1) is (n + 1), 1 < < m - 1. The label of the edges of the cycle are (n -\- l)i - 1, (n -\- l)i - 2, . . . , (n -\- l)i - n, 1 < i < m.

For example, the mean labeling of [P^sub 1^ C^sub 8^] is shown in Figure 9.

Case (ii) ? = 4l+ 1,1= 1,2,3, ..x

Define f:y([P^sub m^;C^sub n^])[arrow right]0,l,2,...q}by

...

The label of the edge .... The label of the edges of the cycle are (n + I)* - 1, (n + I)* - 2, . . . , (n + I)* - n, 1 < i < m.

For example, the mean labeling of [PQ] 65] is shown in Figure 10.

Case (iii) n = 4? + 2, t = l, 2, 3, . . .

Define ...by

...

The label of the edge .... The label of the edges of the cycle are (n + I)i - 1, (n + I)i - 2, . . . , (n + I)i - n, 1 < i < m.

For example, the mean labeling of [P^sub 5^; C^sub 8^] is shown in Figure 11.

Case (iv) n = 4f- 1,t= 1,2,3, ...

Denne f:y([P^sub m^;C^sub n^])[arrow right]0,l,2,...,q}by

...

The label of the edge .... The label of the edges of the cycle are (n + I)i - 1, (n + I)i - 2, . . . , (n + I)i - n, 1 < i < m.

For example, the mean labeling of [P^sub 1^; C^sub 3^] is shown in Figure 12.

Theorem 3.2 [P^sub m^;Q^sub 3^] is a mean graph.

Proof For 1 < j < 8, let VI. be the vertices in the ith copy of Q^sub 3^, 1 < i < p?. Then define f on V[P^sub m^] Q^sub 3^] as follows:

When i is odd.

...

When i is even.

...

The label of the edge .... The label of the edges of the cube are 13i - 1, 13i - 2, . . . , 13i - 12, 1 < i < m.

For example the mean labeling of [P^ Qs] is shown in Figure 13.

Theorem 3.3 [P^sub m^; C^sup (2)^^sub n^ ] is a mean graph.

Proof Let u^sub 1^, u^sub 2^ ... u^sub m^ be the vertices of Pm and the vertices w, 1 < * < m is attached with the center vertex in the ith copy of C^sup (2)^^sub n^ . Let u^sub i^ = V^sub ii^ (center vertex in the ith copy of C^sup (2)^^sub n^).

Let ... be the remaining vertices in the ith copy of C^sup (2)^^sub n^

Then define / on V[^sub P^m: C^sup (2)^^sub n^ ] as follows:

...

Label the vertices of ^. and v' as follows:

Case (i) When n is odd

...

Case (ii) When n is even

...

The label of the edge u^sub i^u^sub i^ is (2n -h 1)*, l < * < m - l and the label of the edges of C^sup (2)^^sub n^ are (2n + I)* - 1, (2n + l)i - 2, . . . , (2n + I)* - 2n for 1 < i < m.

For example the mean labelings of ... are shown in Figure 14.

References

[1] R. Balakrishnan and N. Renganathan, A Text Book on Graph Theory, Springer Verlag, 2000.

[2] S. Somasundaram and R. Ponraj, Mean labelings of graphs, National Academy Science letter, 26 (2003), 210- 213.

[3] S. Somasundaram and R. Ponraj, Non - existence of mean labeling for a wheel, Bulletin of pure and Applied Sciences, (Section E Maths & Statistics) 22E(2003), 103 - 111.

[4] S. Somasundaram and R. Ponraj, Some results on mean graphs, Pure and Applied Mathematika Sciences, 58(2003), 29 - 35.

[5] S. Somasundaram and R. Ponraj, On Mean graphs of order < 5, Journal of Decision and Mathematical Sciences, 9(1 - 3) (2004), 48 - 58.

[6] R. Ponraj and D. Ramya, Super mean labeling of graphs, Reprint.

[7 R. Ponraj and D. Ramya, On super mean graphs of order < 5, Bulletin of Pure and Applied Sciences, (Section E Maths and Statistics) 25E (2006), 143-148.

[8] R. Ponraj and S. Somasundaram, Further results on mean graphs, Proceedings of Sacoeference, August 2005. 443 - 448.

[9] R. Ponraj and S. Somasundaram, Mean labeling of graphs obtained by identifying two graphs, Journal of Discrete Mathematical Sciences and Cryptography, 11 (2) (2008), 239252.

[10] R. Vasuki and A. Nagarajan, Some results on super mean graphs, International Journal of Mathematical Combinatorics, 3(2009), 82-96.

Author affiliation:

Selvam Avadayappan

Department of Mathematics of VHNSN College,

Virudhunagar - 626 001, Tamil Nadu, India

R. Vasuki

Department of Mathematics of Dr.Sivanthi Aditanar College of Engineering,

Tiruchendur- 628 215, Tamil Nadu, India

Email: selvam_avadayappan@yahoo.co.in, vasukisehar@yahoo.co.in

The use of this website is subject to the following Terms of Use