SUPER PAIR SUM LABELLING OF GRAPHS

 SUPER PAIR SUM LABELLING OF GRAPHS


THEOREM:4.1

Any path is a super pair sum graph. 

Proof:

  Let u_1,u_2,…..,u_nbe the vertices of the path p_n.

Case(i) n is odd.

Define f:V(G)∪E(G)→{0,±1,±2,….,±(n-1) as follows:

f(u_i )= {█((i+1-2n)/2  if i is odd@(n+i-1)/2  if i is even )┤  

and f(u_i u_(i+1) )=  (2i-n+1)/2,1≤i≤n-1

thus, f is a super pair sum labelling.

Case(ii). n is even

 Define f:V(G)∪E(G)→{0,±1,±2,….,±(n-1) as follows:

  f(u_i )={█(((3n+2i-4)/2  ,                   (1≤i≤n/2  ,i is odd and n≡2(mod4))¦(2≤i≤n/2,   i is even and n≡0(mod4) ))¦((n+2i-4)/4,                  ((n+4)/2≤i≤n-1,i is odd and n≡2(mod4))¦((n+4)/2≤i≤n,i is even n≡0(mod4) ))@((2-3n+2i)/4   ,                  (2≤i≤(n-2)/2,i is even and n≡2(mod4))¦(1≤i≤(n-2)/2  ,i is odd andn≡0(mod4)))¦((2-5n+2i)/4  ,               ((n+2)/2≤i≤n,i is even and n≡2(mod4))¦((n+2)/2≤i≤n-1,i is odd and n≡0(mod4))))┤  


f(u_i u_(i+1) )=i,for 1≤i≤(n-2)/2,

f(u_n/2,u_(n+2)/2)=0 and

f(u_i u_(i+1) )=i-n,for  (n+2)/2≤i≤n-1

Thus, f is a super pair sum labelling and hence p_n  is a super pair sum graph. 


EXAMPLE:4.1

Super pair sum labelling of P_11,P_12,and P_10 are shown in figure 4.1

Figure 4.1:

Super pair sum labelling of P_11,P_12,and P_10

THEOREM:4.2

Every star graph S_m is a super pair sum graph for m≥1.

Proof:

Let v_0,v_1,….v_(m )be the vertices of the star K_(1,m)  with V_0 as the central vertex. 

Define f:V(G)∪E(G)→{0,±1,±2,….,±m as follows:

f(v_0 )=m,

f(v_i )=i-1-m,1≤i≤m and 

f(v_0 v_1 )=i-1,1≤i≤m

Thus, f is a super pair sum labelling and hence S_m is a super graph for

 m≥1.

THEOREM:4.3

Bistar B_(m,n)is a super pair sum graph for m≥1,n≥1.

Proof:

Let V(k_2 )={u,v}and u_i (1≤i≤m),v_j (1≤j≤n) be the vertices adjacent to u and v edges. 

Define f:V(G)∪E(G)→{0,±1,±2,….,±(m+n+1)} as follows:

f(u)=-(m+n+1);

f(v)=m+n+1-i,1≤i≤m,

f(u_i )= -(m+n+1-j),i≤j≤n,

f(v_i )= -(m+n+1-j),i≤j≤n,

f(uu_i )=-i,1≤j≤n,and 

f(vv_j )=i,1≤j≤n,and 

f(uv)=0  

Thus, f is a super pair sum labelling and hence B_(m,n) is a super pair sum graph for m≥1,n≥1.

EXAMPLE:4.3

A super pair sum labelling of B_7,8 is shown in figure 4.3

Figure 4.3 A super pair sum labelling of B_7,8.

THEOREM:4.4

[P_2n;S_m ] is a super pair sum graph for n≥1,m≥1.

Proof:

Let v_0j,v_1j,….v_(mj ) be the vertices in the j^thcopy of S_m,1≤j≤2n.

The number of the vertices and edges of  [P_2n;S_m ] are 2n(m+1) and 2n(m+1)-1 respectively. 

Case(i) n≡0(mod2)

Define f:V(G)∪E(G)→{0,±1,±2,….,±(2n(m+n+1)-1)} as follows:

f(v_0j )= {█(((m+1)(3n-j+1))/2-1 if j is odd,1≤j≤n-1@1-(m+1)(3n+j)/2  if j is even,2≤j≤n,)┤

f(v_0j )=-f(v_(0_(2n+1-j) ) ),n+1≤j≤2n,

f(v_ij )={█(1-i-(m+)(3n+j-1)/2  if j is odd,1≤j≤n-1@(m+1)(3n-j+2)/2-i-1 if j is even,2≤j≤n,)┤

f(v_ij )= -f(v_(i_(2n+1-j) ) ),n+1≤j≤2n,1≤i≤m,

f(v_oj v_(o_(j+1) ) )= -j(m+1),1≤j≤n-1,

f(v_(o_n ) v_(o_(n+1) ) )=0 

f(v_(0_n ) v_(o_(n+1) ) )=(2n-j)(m+1),n+1≤j≤2n-1,and 


f(v_oj v_(o_(j+1) ) )= {█((i-j)(m+1)-i,1≤i≤m@    (2n-j)(m+1)+i,n+1≤j≤2n,1≤i≤m)┤


Thus, f is a super pair sum labelling 


Case(ii) n≡1(mod2)


Define f:V(G)∪E(G)→{0,±1,±2,….,±(2n(m+1)-1)} as follows:

f(v_oj )= {█((1-(m+1)(3n+j))/2  if j is odd,1≤j≤n@(m+1)(3n-j+1)/2-1 if j is even,2≤j≤n-1.)┤


f(v_oj )= -f(v_(0_(2n+1-j) ) ),n+1≤j≤2n, 


f(v_ij )= {█(((m+1)(3n-j+2))/2-i-1 if j is odd ,1≤j≤n@1-i-(m+1)(3n+j-1)/2  if j is even,2≤j≤n-1)┤


f(v_ij )= -f(v_(i_(2n+1-j) ) ),n+1≤j≤2n,1≤i≤m,


f(v_oj v_(o_(j+1) ) )= -j (m+1),1≤j≤n-1,


f(v_(0_n ) v_(o_(n+1) ) )=0

f(v_(0_j ) v_(o_(j+1) ) )=(2n-j)(m+1),n+1≤j≤2n-1,and 


f(v_oj v_ij )= {█((i-j)(m+1)-i,1≤i≤m@    (2n-j)(m+1)+i,n+1≤j≤2n,1≤i≤m)┤


Thus, f is a super pair sum labelling.

 Hence,[P_2n;S_m ] is a super pair sum graph. 

EXAMPLE:4.4

Super pair sum labelling of 〖[P〗_8,S_3] and [P_6;S_4 ] are shown in figure 4.4

Figure:4.4: super pair sum labelling of 〖[P〗_8,S_3] and [P_6;S_4 ]

THEOREM:4.5

Any comb is a super pair sum graph.

Proof:

Let G be the comb obtained from a path P_n:v_1,v_2,….v_nby joining a vertex u_i to v_i (1≤i≤n)

Case(i) n≡1(mod4)

Define f:V(G)∪E(G)→{0,±1,±2,….,±(2n(m+1)-1)} as follows:

f(v_i )={█(1-2i if i is odd,1≤i≤n@2(n-i)+1 if i is even,1≤i≤n,)┤


f(u_i )={█(f(v_(i+1) )+2,if i is odd,1≤i≤n-1@1 ,if i is even,i=n,)┤

 

f(v_i v_(i+1) )=2n-4i,1≤i≤n-1 and

f(u_i,v_i )=2n-4i+2,1≤i≤n.

Then f is a super pair sum labelling.

Case(ii) n≡3(mod4)

f(v_i )={█(2(n-i)+1 if i is odd,1≤i≤n@ 1-2i if i is even,1≤i≤n,)┤

f(u_i )={█(f(v_(i+1) )+2,if i is odd,1≤i≤n-1@1 ,if i is even,i=n,)┤

f(v_i v_(i+1) )=2n-4i,1≤i≤n-1 and

f(u_i,v_i )=2n-4i+2,1≤i≤n.

Thus, f is super pair sum labelling. When n is even and m=1, the result follows from theorem 4.4

Hence, any comb is super pair sum graph. 

EXAMPLE:4.5

Super pair sum labelling of p_q⨀k_1 and p_11⨀k_1 are shown in figure 4.5

Figure:4.5 Super pair sum labelling of p_q⨀k_1 and p_11⨀k_1 

THEROEM:4.6

C_2n is a super pair sum graph for n≥1.

Proof:

Let v_0j,v_1j,….v_(mj ) be the vertices of the cycle C_2n.

Define f:V(G)∪E(G)→{0,±1,±2,….,±2n} as follows:

f(v_1 )=1, 

f(v_(2i+1) )=1-n-i,1≤i≤[(n-1)/2],

f(v_2i )=2n-i,1≤i≤[n/2],

f(v_i )= -f(v_(i-n) ),n+1≤i≤2n, 

f(v_1 v_2 )=2n,

f(v_i v_(i+1)=n-i+1,2≤i≤n-1,

〖f(v〗_n v_(n+1))=  (3n-2)/2,

〖f(v〗_i v_(i+1))= -f(v_(i-n) v_(i+1-n) ),n+1≤i≤2n-1 and 

〖f(v〗_2n v_1)= -f(v_n v_(n+1) ).

Thus, f is a super pair sum labelling of C_12is shown in figure 4.6.

 Figure.4.6 super pair sum labelling of C_12

THEOREM:4.7

k_(1,m)∪k_(1,n) is a super pair sum graph. 

Proof:

Let u_1,u_2,….u_(m ) be the vertices of  k_(1,m)  and E(k_(1,m) )={u_0 u_i );1≤i≤m}

Let v_0,v_1,….v_n be the vertices of k_(1,m) and E(k_(1,m) )={v_0 v_i );1≤i≤n}

Without loss of generality assume that m<n.

Define f:V(G)∪E(G)→{0,±1,±2,….,±(m+n+1} as follows:

f(u_o )= -(m+n+1)

f(u_i )= m+n+1-2i,1≤i≤m, 

f(v_o )= (m+n+1),

f(v_i )={█(1-2i,1≤i≤m@-m-i,m+1≤i≤n,)┤

f(u_0 u_i )= -2i,1≤i≤m,

f(v_o v_i )={█(m+n-2(i-1),1≤i≤m@ n+1-i,m+1≤i≤n,)┤


 thus,f is  a super pair sum labelling graph and hence, k_(1,m)∪k_(1,n) is a super pair sum graph. 

EXAMPLE:4.7

A super pair sum labelling of k_1,4∪k_1,7 is shown in figure4.7

 

Figure:4.7A super pair sum labelling of k_1,4∪k_1,7

THEOREM:4.8

The caterpillar S(X_1,X_2,….,,X_n )  where, X_1=X_2= …=X_n is a super pair sum graph. 

Proof:

Let u_1,u_2,….u_(m ) be the vertices of the path p_n

The vertex u_1 is attached to X_1=m number of leaves b_(1_j ) (1≤j≤m).

Define f:V(G)∪E(G)→{0,±1,±2,….,±(m+n)} as follows:


f(u_i )={█(-|(2n-i)/2|-m if i is odd and 1≤i≤n,@|(n+i-1)/2|+m if i is even and 2≤i≤n)┤

f(b_(1_j ) )= |(n-1)/2|+j,1≤j≤m, 

f(〖u_1 b〗_(1_j ) )= -m-|n/2|,1≤i≤n-1

Then, f is a super pair sum labelling and hence S(m,0,0,….,0) is a super pair sum graph.

EXAMPLE:

A super pair sum labelling of s(6,0,0,0,0,0,0,0) is shown in figure 4.8

Figure:4.8 A super pair sum labelling of s(6,0,0,0,0,0,0,0).


Comments

Post a Comment

Popular posts from this blog

theorem of graph theory

 THEOREM 1: Let T_0 be minimum cost spanning tree in G. then every in- tree edge in T_0 must be a minimum cost edge in the fundamental cut set associated with it.  Proof:  Let (X;(X)) ̅ be the fundamental cut set associated with the in- tree edge(i;j)in T_0. So, (i;j)is the only in-tree edge in  (X;(X)) ̅, and deletion of (i; j) from T_0disconnects it into smaller trees, one spanning the nodes in X, and the other spanning the nodes in X ̅.   Suppose a minimum cost edge in the cut set (X;(X)) ̅ is an out-of-tree edge (p; q) and not (i; j)    i, e.,         c_pq<c_ij  . then replacing, (i; j) in T_0 by (p; q) leads to spanning tree T_1  with cost = cost of T_0-(c_ij- c_pq) < cost of T_0,  contradicting, the optimality of T_0    hence (i; j) must be minimum cost edge in the fundamental cut set (X;(X)) ̅ associated with it in T_0. THEOREM 2: Let T_0 be minimum cost spanning tree in G. then every in...
Read more

PRIM’S ALGORITHM

Image
  PRIM’S ALGORITHM   Prim’s algorithm is a greedy algorithm that is used to find a minimum spanning tree (MST) of a given connected weighted graph. This algorithm is preferred when the graph is dense. The dense graph is a graph in which there is a large number of edges in the graph. This algorithm can be applied to only undirected connected graph and there should not be any negative weighted edge. In this case, the algorithm is quite efficient. Since there are no non-negative weight cycles, there will be a shortest path whenever there is a path.             The steps to find minimum spanning tree using Prim’s algorithm are as follows: 1. If graph has loops and parallel edges than remove loops and parallel edges of that graph. 2. Randomly choose any node, labelling it with a distance of 0 and all other nodes as ∞. The chosen node is treated as current node and considered as visited. All other nodes are considered as unvisited....
Read more
  ALGEBRA What is Algebra? Algebra helps solve the mathematical equations and allows to derive unknown quantities, like the bank interest, proportions, percentages. We can use the variables in the algebra to represent the unknown quantities that are coupled in such a way as to rewrite the equations. The algebraic formulas are used in our daily lives to find the distance and volume of containers and figure out the sales prices as and when needed. Algebra is constructive in stating a mathematical equation and relationship by using letters or other symbols representing the entities. The unknown quantities in the equation can be solved through algebra. Some of the main topics coming under algebra include Basics of algebra, exponents, simplification of algebraic expressions, polynomials, quadratic equations, etc Branches of Algebra As it is known that,  algebra is the concept based on unknown values called variables. The important concept of algebra is equations. It follows various...
Read more