Printer Friendly

RELATION BETWEEN MEAN LABELING AND (A,D)-EDGE-ANTIMAGIC VERTEX LABELING.

Byline: Ali Ahmad, Muhammad Imran and Andrea Semanicova-Fenovcikova

ABSTRACT

An injective mapping (Equation) is called mean labeling of (Equation) if the induced edge function (Equation) defined as (Equation) is bijective.

A bijective mapping (Equation) is called an (Equation) -edge-antimagic vertex labeling, if the set of edge-weights (Equation) forms an arithmetic sequence with the intial term (Equation) and the difference (Equation), where (Equation) is a positive and is a nonnegative integer.

In this paper, we study the relation between mean labeling and (Equation) -edge-antimagic vertex labeling. Moreover, we show that two classes of caterpillars admit mean labeling.

The work was supported by Slovak VEGA Grant 1/0130/12.

NOTATION AND PRELIMINARY RESULTS

As a standard notation, assume that (Equation) is a finite simple and undirected graph. A labeling of a graph is any mapping that sends some set of graph elements to a set of numbers (usually positive integers). If the domain is the vertex-set or the edge-set, the labelings are called respectively vertex-labelings or edge-labelings. If the domain is (Equation) then we call the labeling a total labeling. In many cases it is interesting to consider the sum of all labels associated with a graph element. This will be called the weight of the graph element.

An injective mapping is called mean labeling of (Equation) if the induced edge function (Equation) defined as

For every, is a bijection. A graph that admits a mean labeling is called a mean graph. On Figure 1 is illustrated a mean graph with the corresponding mean labeling.

The concept of mean labeling was introduced by Somasundaram and Ponraj [5]. In [4, 5, 6, 7] and [8] they prove the following graphs are mean graphs:

, , , , , , triangular snake, triangular snakes, quadrilateral snakes, (Equation) if and only if n less than 3, (Equation) if and only if n less than 3, bistars (Equation) if and only if m less than n+2, the subdivision graph of the star (Equation) if and only if n less than 4, and the friendship graph (Equation) if and only if t less than 2. They also prove that (Equation) is not a mean graph for n greater than 3 and enumerate all mean graphs of order less than 5. Finding the mean labeling seems to be hard even for simple graphs, see [2].

Let a greater than 0 and (Equation) are two fixed integers. A labeling is called an (Equation) -edge-antimagic vertex labeling, for short (Equation) -EAV labeling, if the set of the edge-weights forms an arithmetic sequence with the initial term a and the difference d, i.e.

A graph that admits an -EAV labeling is called an -EAV graph. For more detail see [1, 3, 9].

A caterpillar is a tree that can be converted into a path or a single vertex by deleting all vertices of degree one. We will deal with two types of caterpillars.

(Equation)

In this paper, we study properties -EAV labeling and mean labeling and we prove that the comb graph (Equation) and the special caterpillar (Equation) are the mean graphs.

RELATION BETWEEN MEAN LABELING AND (a,d) -EAV LABELING

The main result in this section is given in the following theorem.

Theorem 1. If G is an -EAV graph, , then G is also a mean graph.

Proof. Let G be an (a, d)-EAV graph. Thus, there exists an (a, d)-EAV labeling f of G,

(Equation)

We consider an edge function g of the graph G defined in the following way

(Equation)

Now we will consider two cases according to the parity of the difference d.

Case 1. (Equation)

In this case the edge-weights under the labeling f have the same parity. For (Equation) the edge-weights are even and we have

For (Equation) the edge-weights are odd thus we obtain

As (Equation), in both subcases the induced labeling g is a bijective mapping and thus f is a mean labeling of G.

Case 1. (Equation)

In this case the edge-weights under the labeling f have the alternating parity. For (Equation) we get

For (Equation) we have

As (Equation), in both subcases the induced labeling g is a bijective mapping and thus f is a mean labeling of G.

MEAN LABELING OF SOME CLASSES OF CATERPILLARS

For the comb graph we proved.

Theorem 2. For every positive integer n the comb Cb is a mean graph.

Proof. Let n be a positive integer. We define the labeling (Equation) in the following way

(Equation)

For the induced edge labeling g of labeling f we have

(Equation)

It is easy to see that g is a bijective function that assigns the consecutive integers (Equation) to the edges of . Therefore Cb is a mean graph.

Theorem 3. For every positive integere r n caterrpillar Sc is a mean graph.

Proof. Let n be a positive integer. We define the vertex labeling f for (Equation) as follows:

(Equation)

For the induced edge labeling g of f we get.

(Equation)

It is easy to see that g assigns the consecutive integers (Equation) to the edges of (Equation). Therefore (Equation) is a mean graph. (Equation)

CONCLUSION

In this paper we mention the relationship between the mean labeling and the (a, d)-edge-antimagic vertex labeling. For further investigation we recall to find relationship between the mean labeling and a graceful labeling or -labeling or other kind of labeling. Moreover, we prove that the comb graph and special caterpillar are mean graphs.

REFERENCES

[1] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math., 231, 153-168 (2001).

[2] J. Gallian, A dynamic survey of graph labeling, The Electronic J. Combin., 17, (2011).

[3] M. Hussain, Slamin and E.T. Baskoro, On super edge-magic total labeling of banana trees, Utilitas Mathematica, 79, 243-251 (2007).

[4] R. Ponraj and S. Somasundaram, Further results on mean graphs, Proc. SACOEFERENCE, National Level Conference, Dr. Sivanthi Aditanar College of Engineering,, 443-448(2005).

[5] S. Somasundaram and R. Ponraj, Mean labelings of graphs, Nat. Acad. Sci. Let., 26, 210-213(2003).

[6] S. Somasundaram and R. Ponraj, Non-existence of mean labeling for a wheel, Bull. Pure and Appl. Sciences (Mathematics and Statistics), 22E 103-111(2003).

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

[8] S. Somasundaram and R. Ponraj, On mean graphs of order less than 5, J. Decision and Mathematical Sciences, 9 47-58(2004).

[9] W.D. Wallis, E.T. Baskoro, M. Miller and Slamin, Edge-magic total labelings, Australas. J. Combin., 22, 177-190(2000).

College of computer and information system, Jazan University, Jazan, Saudi Arabia, 2Center for Advanced Mathematics and Physics (CAMP), National University of Science and Technology (NUST), H-12 Sector, Islamabad, Pakistan., 3Department of Appl. Mathematics and Informatics, Technical University, Kosice, Slovak Republic.
COPYRIGHT 2012 Asianet-Pakistan
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2012 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ahmad, Ali; Imran, Muhammad; Semanicova-Fenovcikova, Andrea
Publication:Science International
Article Type:Report
Geographic Code:4EXSV
Date:Mar 31, 2012
Words:1130
Previous Article:A NUMERICAL TECHNIQUE FOR HEAT EQUATION SUBJECT TO INTEGRAL SPECIFICATIONS.
Next Article:COMPUTER AIDED PROCESS PLANNING: AN INTEGRATED APPROACH TOWARD MANUFACTURING SUSTAINABILITY.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters