ABSTRACT

Let G be a graph. An injective map is called a pair sum labeling if the induced edge function, defined by is one-one and is either of the form or according as q is even or odd. A graph with a pair sum labeling is called a pair sum graph. In this paper we investigate the pair sum labeling behavior of subdivision of some standard graphs.

1. Introduction

The graphs considered here will be finite, undirected and simple. and will denote the vertex set and edge set of a graph G. The cardinality of the vertex set of a graph G is denoted by p and the cardinality of its edge set is denoted by q. The corona of two graphs and is defined as the graph obtained by taking one copy of (with vertices) and copies of and then joining the ith vertex of to all the vertices in the ith copy of. If e = uv is an edge of G and w is a vertex not in G then e is said to be subdivided when it is replaced by the edges uw and wv. The graph obtained by subdividing each edge of a graph G is called the subdivision graph of G and it is denoted by. The graph is called the ladder. A dragon is a graph formed by joining an end vertex of a path to a vertex of the cycle. It is denoted as. The triangular snake is obtained from the path by replacing every edge of a path by a triangle. The quadrilateral snake is obtained from the path by every edge of a path is replaced by a cycle. The concept of pair sum labeling has been introduced in [1]. The Pair sum labeling behavior of some standard graphs like complete graph, cycle, path, bistar, and some more standard graphs are investigated in [1-3]. That all the trees of order ≤9 are pair sum have been proved in [4]. Terms not defined here are used in the sense of Harary [5]. Let x be any real number. Then stands for the largest integer less than or equal to x and stands for the smallest integer greater than or equal to x. Here we investigate the pair sum labeling behavior of, for some standard graphs G.

2. Pair Sum Labeling

Definition 2.1. Let G be a graph. An injective map is called a pair sum labeling if the induced edge function, defined by is one-one and is either of the form

or

according as q is even or odd. A graph with a pair sum labeling defined on it is called a pair sum graph.

Theorem 2.2 [1]. Any path is a pair sum graph.

Theorem 2.3 [1]. Any cycle is a pair sum graph.

3. On Standard Graphs

Here we investigate pair sum labeling behavior of and.

Theorem 3.1. If n is even, is a pair sum graph.

Proof. Let be the cycle and let be the path.

Case 1.

Define

by

.

Here

Therefore f is a pair sum labeling.

Case 2.

Define

by

Here

Hence f is a pair sum labeling.

Case 3.

Label the vertex, as in Case 1. Then label to.

Case 4.

Assign the label to and assign the label to the remaining vertices as in Case 2.

Illustration 1. A pair sum labeling of is shown in Figure 1.

Theorem 3.2. is pair sum graph if n is even.

Proof: Let be the vertices of and u, v, w, z. be the vertices in Let

and

Define

by

Here

Therefore f is a pair sum labeling.

Illustration 2. A pair sum labeling of is shown in Figure 2.

4. On Subdivision Graph

Here we investigate the pair sum labeling behavior of for some standard graphs G.

Theorem 4.1. is a pair sum graph, where is a ladder on n vertices.

Proof. Let

Let

Case 1: n is even.

When n = 2, the proof follows from the Theorem 2.3. For n > 2Define

by

When n = 4,

For n > 4,

Therefore f is a pair sum labeling.

Case 2. n is odd.

Clearly and hence is a pair sum graph by Theorem 2.2. For n > 1Define

by

Therefore

and

when n > 5,

Then f is a pair sum labeling.

Illustration 3. A pair sum labeling of is shown in Figure 3.

Theorem 4.2. is a pair sum graph Proof. Let

Let

Case 1. n is even.

Define

by

Here

Then f is pair sum labeling.

Case 2. n is odd.

Define

by

Here

Then f is pair sum labeling.

Illustration 4. A pair sum labeling of is shown in Figure 4.

Theorem 4.3. is a pair sum graph.

Proof. Let

Let

Case 1. n is even.

When n = 2, the proof follows from Theorem 2.2. For n > 2, Define

by

Here

For n > 4,

Then f is pair sum labeling.

Case 2. n is odd.

Since, which is a pair sum graph by Theorem 2.3. For n > 1, Define

by

Here

When n > 5,

Then f is pair sum labeling.

Illustration 5. A pair sum labeling of is shown in Figure 5.

Theorem 4.4. is a pair sum graph where is a triangular snake with n triangle.

Proof. Let

and

Case 1. n is even.

When n = 2, Define f(u₁) = 7, f(u₂) = 6, f(u₃) = 1, f(u₄) = –6, f(u₅) = –7, f(v₁) = 5, f(v₂) = 2, f(v₃) = –4, f(v₄) = –5, f(w₁) = 3, f(w₂) = –3. When n > 2, Define

by

For n = 4,

For n > 4

Then f is pair sum labeling.

Case 2. n is odd.

Clearly, and hence is a pair sum graph by Theorem 2.3.

For > 1, Define

by

,

Here n = 3,

For n > 3,

Then f is pair sum labeling.

Illustration 6. A pair sum labeling of is shown in Figure 6.

Theorem 4.5. is a pair sum graph.

Proof. Let

and

Case 1. n is even.

When n = 2, Define f(u₁) = 11, f(u₂) = 6, f(u₃) = 1,  f(u₄) = –6, f(u₅) = –11, f(w₁) = 9, f(w₂) = 2, f(w₃) = –4, f(w₄) = –9, f(v₁) = 7, f(v₂) = 5, f(v₃) = 3, f(v₄) = –3, f(v₅) = –5, f(v₆) = –7. When > 2, Define

by

Here

Then f is pair sum labeling.

Case 2. n is odd.

is a pair sum graph follows from Theorem 2.3.When n > 1. Define

by

For n = 3,

n > 3,

Then f is pair sum labeling Illustration 7. A pair sum labeling of is shown in Figure 7.

5. Acknowledgements

We thank the referees for their valuable comments and suggestions.

REFERENCES