# 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).