Printer Friendly

Magic graphoidal on special type of unicyclic graphs.

[section]1. Introduction

By a graph, we mean a finite simple and undirected graph. The vertex set and edge set of a graph G denoted are by V(G) and E(G) respectively. [C.sup.+.sub.n] is a crown, [C.sub.n] [dot encircle] [P.sub.n] is a Dragon and [C.sub.m] [dot encircle] [P.sub.n] is a Armed Crown. Terms and notations not used here are as in [3].

[section]2. Preliminaries

Let G = {V, E} be a graph with p vertices and q edges. A graphoidal cover [psi] of G is a collection of (open) paths such that

[1] Every edge is in exactly one path of [psi].

[2] Every vertex is an interval vertex of atmost one path in [psi].

We define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [zeta] is the collection of graphoidal covers [psi] of G and [gamma] is graphoidal covering number of G.

Let [psi] be a graphoidal cover of G. Then we say that G admits [psi]-magic graphoidal total labeling of G if there exists a bijection f : V [union] E [right arrow] {1, 2,...,p + q} such that for every path P = ([v.sub.0][v.sub.1][v.sub.2]...[v.sub.n]) in [psi], then f*(P) = f ([v.sub.0]) + f ([v.sub.n]) + [n.summation over (1)] f ([v.sub.i-1][v.sub.i] = k, a constant, where f* is the induced labeling of [psi]. A graph G is called magic graphoidal if there exists a minimum graphoidal cover [psi] of G such that G admits [psi]- magic graphoidal total labeling. In this paper, we proved that Crown [C.sup.+.sub.n], Dragan [C.sub.n] [dot encircle] [P.sub.n] and Armed grown [C.sub.m] [dot encircle] [P.sub.n] is graph in which a path of length n is joined at every vertex of the cycle [C.sub.m] are magic graphoidal.

Result 2.1. [11] Let G = (p, q) be a simple graph. If every vertex of G is an internal vertex in [psi] then [gamma](G) = q - p.

Result 2.2. [11] If every vertex v of a simple graph G, where degree is more than one ie d(v) > 1, is an internal vertex of [psi] is minimum graphoidal cover of G and [gamma](G) = q - p + n where n is the number of vertices having degree one.

Result 2.3. [11] Let G be (p, q) a simple graph then [gamma](G) = q - p +1 where t is the number of vertices which are not internal.

Result 2.4. [11] For any tree G, [gamma](G) = [DELTA] where [DELTA] is the maximum degree of a vertex in G.

Result 2.5. For any k-regular graph G, k [greater than or equal to] 3, [gamma](G) = q - p.

Result 2.6. For any graph G with [delta] [greater than or equal to] 3, [gamma](G) = q - p.

Result 2.7. Let G be a connected unicyclic graph with n vertices of degree 1, Z be its unique cycle and let m be the number of vertices of degree at least 3 on Z. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[section]3. Magic graphoidal on special type of unicyclic graphs

Theorem 3.1. Crown [C.sup.+.sub.n] is magic graphoidal.

Proof. Let V([C.sup.+.sub.n]) = {[u.sub.i], [v.sub.i] : 1 [less than or equal to] i [less than or equal to] n}, E[C.sup.+.sub.n] = {[([u.sub.i][u.sub.i]+1) : 1 [less than or equal to] i [less than or equal to] n - 1] [union] ([u.sub.1][u.sub.n]) [union] ([u.sub.i][v.sub.i]) : 1 [less than or equal to] i [less than or equal to] n}. Define f : V [union] E [right arrow] {1, 2, 3,...,p + q} by

f([u.sub.i]) = i, 1 [less than or equal to] i [less than or equal to] n;

f([v.sub.1]) = 3n +1;

f([v.sub.i]+1) = 4n + 1 - i, 1 [less than or equal to] i [less than or equal to] n - 1;

f([u.sub.i][u.sub.i]+1) = 3n + 1 - i, 1 [less than or equal to] i [less than or equal to] n - 1;

f([u.sub.1][u.sub.n]) = 2n + 1;

f([u.sub.1][v.sub.1]) = 2n;

f([u.sub.i][v.sub.i]) = n + (i - 1), 2 [less than or equal to] i [less than or equal to] n.

Let [psi] = {[([u.sub.i][u.sub.i+1][v.sub.i+1]) : 1 [less than or equal to] i [less than or equal to] n - 1] [union] ([u.sub.n][u.sub.1][v.sub.1])}. Clearly, [psi] is a minimum graphoidal cover.

[f.sup.*][[u.sub.n][u.sub.1][v.sub.1])] = f([u.sub.n]) + f([v.sub.1]) + f([u.sub.n][u.sub.1]) + f ([u.sub.1][v.sub.1]) = n + 3n + 1 + 2n + 1 + 2n = 8n + 2. (1)

For 1 [less than or equal to] i [less than or equal to] n - 1,

[f.sup.*][([u.sub.i][u.sub.i+1][v.sub.i+1])] = f([u.sub.i]) + f([v.sub.i+1]) + f(([u.sub.i][u.sub.i+1]) + f([u.sub.i+1][v.sub.i+1])) = i + 4n + 1 - i + 3n + 1 - i + n + i = 8n + 2. (2)

From (1) and (2), we conclude that [psi] is minimum magic graphoidal cover. Hence, Crown [C.sup.+.sub.n] is magic graphoidal. For example, the magic graphoidal cover of [C.sup.+.sub.4] is shown in Figure 1.

[FIGURE 1 OMITTED]

[psi] = {([u.sub.1][u.sub.2][v.sub.2]), ([u.sub.2][u.sub.3][v.sub.3]), ([u.sub.3][u.sub.4][v.sub.4]), ([u.sub.4][u.sub.1][v.sub.1])}, [gamma] = 4, K = 34.

Theorem 3.2. Dragan [C.sub.n] [dot encircle] [P.sub.n], (n -even) is magic graphoidal.

Proof. Let G = [C.sub.n] [dot encircle] [P.sub.n].

Let V(G) = {[[u.sub.i],[v.sub.i] : 1 [less than or equal to] i [less than or equal to] n - 1],[u.sub.n]}; E(G) = {[([u.sub.i][u.sub.i+1]) : 1 [less than or equal to] i [less than or equal to] n - 1] [union] ([u.sub.1][u.sub.n]) [union] ([u.sub.n][v.sub.n-1]) [union] [([v.sub.i][v.sub.i+1]) : 1 [less than or equal to] i [less than or equal to] n - 2]}.

Define f : V [union] E [right arrow] {1, 2, 3,...,p + q} by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

From (3) and (4), we conclude that [psi] is minimum magic graphoidal cover. Hence, [C.sub.n] [dot encircle] [P.sub.n,] (n-even) is magic graphoidal. For example, the magic graphoidal cover of [C.sub.6] [dot encircle] [P.sub.6] is shown in Figure 2.

[FIGURE 2 OMITTED]

[psi] = {([u.sub.1][u.sub.2][u.sub.3][u.sub.4][u.sub.5][u.sub.6]), ([v.sub.1][v.sub.2][v.sub.3][v.sub.4][v.sub.5][u.sub.6] [u.sub.1])},[gamma] = 2, K = 115.

Theorem 3.3. Dragan [C.sub.n] [dot encircle] [P.sub.n], (n-odd) is magic graphoidal cover.

Proof. Let G = [C.sub.n] [dot encircle] [P.sub.n].

Let V(G) = {[u.sub.i], [v.sub.i] : 1 [less than or equal to] i [less than or equal to] n - 1, [u.sub.n]};

E(G) = {[([u.sub.i][u.sub.i+1]) : 1 [less than or equal to] i [less than or equal to] n - 1] [union] ([u.sub.1] [u.sub.n]) [union] ([u.sub.n][v.sub.n-i]) [union] [([v.sub.i][v.sub.i+1]) : 1 [less than or equal to] i [less than or equal to] n - 2]}.

Define f : V [union] E [right arrow] {1, 2, 3,...,p + q} by

f([v.sub.i]) = i, 1 [less than or equal to] i [less than or equal to] n - 1;

f([u.sub.1]) = 4n - 2;

f([u.sub.i]) = n + (i - 2), 2 [less than or equal to] i [less than or equal to] n;

f([u.sub.n]) = f(vn) = 2n - 1;

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

f ([u.sub.1][u.sub.n]) = 2n - 2;

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [psi] = {([u.sub.1][u.sub.2]... [u.sub.n]), ([v.sub.1][v.sub.2]... [v.sub.n- 1][u.sub.n][u.sub.1])}. Clearly, [??](G) = 2.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

From (5) and (6), we conclude that [psi] is minimum magic graphoidal cover. Hence, [C.sub.n] [dot encircle] [P.sub.n], (n-odd) is magic graphoidal. For example, the magic graphoidal cover of [C.sub.5] [dot encircle] [P.sub.5] is shown in Figure 3.

[FIGURE 3 OMITTED]

[psi] = {([u.sub.1][u.sub.2][u.sub.3][u.sub.4][u.sub.5]), ([v.sub.1][v.sub.2][v.sub.3][v.sub.4][v.sub.5][u.sub.1])}, [gamma] = 2, K = 81.

Theorem 3.4. Armed grown [C.sub.m][[??].sub.n] is magic graphoidal.

Proof. Let G = [C.sub.m] [dot encircle] [P.sub.n].

Let V(G) = {[v.sub.i] : 1 [less than or equal to] i [less than or equal to] m, [u.sub.ij] :1 [less than or equal to] i [less than or equal to] m, 1 [less than or equal to] j [less than or equal to] n}; E(G) = {[([v.sub.i][v.sub.i+1]) : 1 [less than or equal to] i [less than or equal to] m - 1] [union] ([v.sub.1][v.sub.m]) [union] ([u.sub.ij][u.sub.ij+1]) :1 [less than or equal to] i [less than or equal to] m, 1 [less than or equal to] j [less than or equal to] n - 1}.

Let [v.sub.1] = [u.sub.m1], [v.sub.i] = [u.sub.(i-1)1], 2 [less than or equal to] i [less than or equal to] m.

Let [psi] = {([v.sub.i][v.sub.i+1][u.sub.i2][u.sub.i3]... [u.sub.in]), 1 [less than or equal to] i [less than or equal to] m - 1 [union] ([v.sub.m][v.sub.1][u.sub.m2][u.sub.m3]... [u.sub.mn])}.

Case (i) n is even.

Define f : V [union] E [right arrow] {1, 2,...,p + q} by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

For 1 [less than or equal to] i [less than or equal to] m - 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

From (7) and (8), we conclude that [psi] is minimum magic graphoidal cover. Hence, [C.sub.m] [dot encircle] [P.sub.n] (n-even) is magic graphoidal. For example, the magic graphoidal cover of [C.sub.4] [dot encircle] [P.sub.4] is shown in Figure 4.

[FIGURE 4 OMITTED]

[psi] = {([v.sub.1][v.sub.2][u.sub.12][u.sub.13][u.sub.14]), ([v.sub.2][v.sub.3][u.sub.22][u.sub.23][u.sub.24]), ([v.sub.3][v.sub.4][u.sub.32][u.sub.33][u.sub.34]), ([v.sub.4][v.sub.1][u.sub.42][u.sub.43][u.sub.44])}, [gamma] = 4, K = 75

Case (ii) n is odd.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

For 1 [less than or equal to] i [less than or equal to] m - 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

From (9) and (10), we conclude that [psi] is minimum magic graphoidal cover. Hence, [C.sub.m] [dot encircle] [P.sub.n] (n-odd) is magic graphoidal. For example, the magic graphoidal cover of [C.sub.3] [dot encircle] [P.sub.5] is shown in Figure 5.

[FIGURE 5 OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

References

[1] B. D. Acarya and E. Sampath Kumar, Graphoidal covers and Graphoidal covering number of a Graph, Indian J. pure appl. Math., No. 10, 18(1987), 882-890.

[2] J. A. Gallian, A Dynamic Survey of graph labeling, The Electronic journal of Coim- binotorics, 6(2001), #DS6.

[3] F. Harary, Graph Theory, Addition-Wesley publishing company Inc, USA, 1969.

[4] A. Nellai Murugan and A. Nagarajan, Magic Graphoidal on Trees (Communicated).

[5] A. Nellai Murugan and A. Nagarajan, Magic Graphoidal on Join of two graphs (Com- municated).

[6] A. Nellai Murugan and A. Nagarajan, Magic Graphoidal on Path related graphs (Com- municated).

[7] A. Nellai Murugan and A. Nagarajan, On Magic Graphoidal graphs (Communicated).

[8] A. Nellai Murugan and A. Nagarajan, Magic Graphoidal on product graphs (Commu- nicated).

[9] A. Nellai Murugan and A. Nagarajan, Magic Graphoidal on special types of graphs (Communicated).

[10] A. Nellai Murugan and A. Nagarajan, Magic Graphoidal on special class of graphs (Communicated).

[11] C. Packiam and S. Arumugam, On the Graphoidal covering number of a Graph, Indian J. pure. appl. Math., 20(1989), 330-333.

A. Nellai Murugant ([dagger]) and A. Nagarajan ([double dagger])

Department of Mathematics, V. O. Chidambaram College, Tuticorin, Tamilnadu

E-mail: anellai.vocc@gmail.com
COPYRIGHT 2011 American Research Press
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

 Reader Opinion

Title:

Comment:



 

Article Details
Printer friendly Cite/link Email Feedback
Author:Murugan, A. Nellai; Nagarajan, A.
Publication:Scientia Magna
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2011
Words:2225
Previous Article:Implicative filters in pocrims.
Next Article:Minimal translation lightlike hypersurfaces of semi-euclidean spaces.
Topics:

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