Printer Friendly

VERTEX EQUITABLE LABELING OF SUPER SUBDIVISION GRAPHS.

Byline: P.Jeyanthi, A. Maheswari and M.Vijayalakshmi

ABSTRACT

Let G be a graph with p vertices and q edges and (Eq.) vertex labeling (Eq.) induces. an edge labeling f defined by f (uv) = f(u) + f(v) for all edges uv. For a A , let vf (a) be the number of vertices v with f(v) = a. A graph G is said to be vertex equitable if there exists a vertex labeling f such that for all a and b in A, (Eq.) and the induced edge labels are 1, 2, 3,..., q. In this paper, we prove that the graphs (Eq.) and S (Qn) of quadrilateral snake are vertex equitable.

Keywords: Vertex equitable labeling, vertex equitable graph

1. INTRODUCTION:

All graphs considered here are simple, finite, connected and undirected .We follow the basic notations and terminologies of graph theory as in [1]. A graph labeling is an assignment of integers to the vertices or edges or both, subject to certain conditions. There are several types of labeling and a detailed survey of graph labeling can be found in [2]. The vertex set and the edge set of a graph are denoted by V(G) and E(G) respectively. The concept of vertex equitable labeling was due to Lourdusamy and Seenivasan in [3] and further studied in [4,5,6,7,8,9]. Let G be a graph with p vertices and q edges and (EQUATION). A graph G is said to be vertex equitable if there exists a vertex labeling (EQUATION) that induces an edge labeling f defined by f (uv) = f(u) + f(v) for all edges uv such that (EQUATION) for all a and b in A, and the induced edge labels are 1, 2, 3,..., q, where vf (a) be the number of vertices v with f(v ) = a for a A . The vertex labeling f is known as vertex equitable labeling.

A graph G is said to be a vertex equitable if it admits vertex equitable labeling. The corona G1 G2 of the graphs G1 and G2 is defined as a graph obtained by taking one copy of G1 (with p vertices) and p copies of G2 and then joining the ith vertex of G1 to every vertex of the ith copy of G2. A cartesian product of two graphs G1 and G2 is the graph G1 G2 such that its vertex set is a cartesian product of V(G1) and V(G2) i.e. (EQUATION) edge set is defined as (EQUATION). The comb Pn K1 is agraph obtained by joining a single pendant edge to each vertex of a path Pn .The bistar Bm,n is a graph obtained from K2 by joining m pendant edges to one end of K2 and n pendant edges to the other end of K2. The graph Pn P2 is called a ladder graph. The quadrilateral snake D(Qn) is a graph obtained from a path Pn with vertices u1, u2 , ..., un by joining ui and ui+1 to the new vertices vi , xi respectively and then joining vi , xi for i=1,2,...,n-1. Let G be a graph.

The super subdivision graph S (G) is obtained from G by replacing every edge e of G by a complete bipartite graph K2,m (m 2) in such a way that the ends of e are merged with the two vertices of the 2-vertices part of K2,m after removing the edge e from G. We use the following known results in the subsequent theorems.

Theorem 1.1 [9] Let G1(p1,q1), G2(p2,q2) ,..., Gm (pm ,qm) be a vertex equitable graphs with qi's are even(i=1,2,...,m) and ui , vi be the vertices of Gi (1 i m) labeled by 0 and a/2. Then the graph G obtained by identifying v1 with u2 and v2 with u3 and v3 with u4 and so on until we identify vm1 with um is a vertex equitable graph.

(EQUATION)

Theorem 1.2 [3] The super subdivision graph Cn is vertex equitable if n 0 or 3(mod4) ,.

2. MAIN RESULTS

Theorem 2.1: The super subdivision graph S (Pn K1) is a vertex equitable graph.

(EQUATIONS)

Theorem 2.2. The super subdivision graph S (B(n ,n)) is a vertex equitable graph.

(EQUATIONS)

Hence S (B(n ,n)) is a vertex equitable graph.

Example 2. The vertex equitable labeling of the super subdivision graph S (B(2,2)) is given in Figure 2.

Theorem 2.3 The super subdivision graph S (Pn P2) is a vertex equitable graph.

(EQUATIONS)

Example 3. The vertex equitable labeling of the super subdivision graph, S ( P4 P2) is given in Figure3.

Theorem 2.4 The super subdivision graph S (Qn) is a vertex equitable graph

Proof: By Theorem 1.2, S (Q) is a vertex equitable graph.

Let (EQUATION) and ui, vi be the vertices with labels 0 and a/2 respectively. By Theorem 1.1, the graph S (Qn) admits vertex equitable labeling.

Example 2.8 The vertex equitable labeling of S (Q3) is given in Figure 4.

REFERENCES

[1] Harary.F, Graph theory, Addison Wesley, Massachusetts, (1972).

[2] Gallian J.A , A Dynamic Survey of graph labeling, The Electronic Journal of Combinatorics, #DS6, 2014.

[3] Lourdusamy .A and Seenivasan. M , Vertex equitable labeling of graphs, Journal of Discrete Mathematical Sciences andCryptography,11(6):727-735(2008).

[4] Jeyanthi .P and Maheswari .A, Some Results on Vertex Equitable Labeling, Open Journal of Discrete Mathematics, 2): 51-57 (2012).

[5] Jeyanthi .P and Maheswari .A, Vertex equitable labeling of Transformed Trees, Journal of Algorithms and Computation 44 :9 -20 (2013).

[6] Jeyanthi .P and Maheswari .A, Vertex equitable labeling of cyclic snakes and bistar graphs, Journal of Scientific Research, Vol. 6,No.1(2014),79-85.

[7] Jeyanthi .P and Maheswari .A, Vertex equitable labeling of cycle and path related graphs,Utilitas Mathematica, (to appear).

[8] Jeyanthi .P and Maheswari .A and Vijayalakshmi.M, Vertex equitable labeling of double alternate snake graphs, (preprint).

[9] Jeyanthi .P and Maheswari .A, and Vijayalakshmi.M , New results on vertex equitable labeling, (preprint).
COPYRIGHT 2015 Asianet-Pakistan
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Publication:Science International
Article Type:Report
Geographic Code:9PAKI
Date:Oct 31, 2015
Words:1018
Previous Article:HADAMARD'S TYPE INEQUALITIES FOR FUNCTIONS WHOSE ABSOLUTE VALUES OF FIRST DERIVATIVE ARE -CONVEX.
Next Article:MODELLING OUTPUT GROWTH MEASUREMENT OF MACHINERY MANUFACTURING SMES.
Topics:

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