Algorithmic implementation of signed product and total signed product cordial labeling on complex graph

Abstract

Apart from other labeling signed product and total signed product labeling already have been applied on different kind of graphs. Signed product cordial labeling for the graph G = (V, E), where each vertex is labelled by 1 or -1 and edge label is induced by multiplication of two of it end vertices with the following restriction that the absolute difference between total number of vertices labelled by 1 and -1 is at most 1, similarly for the edges also. Total signed product cordial labeling follows property that absolute difference between total number of vertices and edges labelled by -1 and total number of vertices and edges labelled by 1 is at most 1. In this paper, we have considered Cartesian product between two balanced bipartite graphs and apply above labeling on it. We have designed some suitable algorithms which will driven by any kind of computer programming language. Illustration with example and complexity of the algorithms are analysed successfully.

Keywords

Cartesian product Signed product cordial labeling Total signed product cordial labeling complete bipartite graph

1 Introduction

Graph labeling is a modified form of vertex coloring problem which was introduced by A. Rosa [17] in 1967. Gallian [1] has done a precious work on graph labeling along with different applications. Hegde [3] described labeling problem by considering a set of values from which the labels are taken under a confined environment and some rules are impose by which each edges are label. Beineke and Hegde [4] explain graph labeling as a combination of graph theory and number theory. Griggs and Yeh [2] worked in different direction of graph labeling although their contribution can not be avoided.

Graph labeling scheme has already been appiled on so many needful area. I. Cahit [5 –15] bring the idea of cordial labeling from both graceful [17] and harmonious [16] labelings. Cahit [6] also proved there exist some graphs which are cordial graphs.

Signed product cordial labeling is also a modified part of cordial labeling which was initiated by J. Baskar Babujee [18] and he claims that there exist few graphs where signed product cordial labeling can be use. This concept further explored by so many researchers like P.P. Ulaganathan et al. [19], Santhi. M [21] and Santhi. M et al. [20, 22] etc. Vaidya and Shah [23, 24] have applied cordial labeling on snake graph and bi-star graph. Some more important works also been done in this labeling which was applied on some simple graphs, on some new types of complex graphs. Here we consider a complex graph structure which was obtained by doing Cartesian product between two balanced bipartite graph i.e G = K_n,n × K_n,n. Few realistic work done by Amanthulla et al. [25, 26] on different labeling which may lead to introduce a new direction to this labeling realm.

Traditional network are very complex and global in nature, where each node is connected with all other nodes so that it can accessed for full information at any time apart from failure of one or more nodes. Social networks and others hybrid network are complex due to large number of base users, so graph labeling of such networks become very hard. In our considering graph structure we carefully investigate the complex structure to a simple pattern then proceed for labeling. Solving of complex structure in a simple way can give us a new direction of research. Here we design an algorithm of cordial labeling for the graph obtained by Cartesian product between two balanced bipartite graph and analyse the time complexity also.

The remaining work of the paper is presented as Section explain some related definition and lemma. Section 3 describe the main portion of the work and its contains three algorithms, analysis of algorithm and correctness of each algorithm.

2 Preliminaries

Definition 1. A vertex labeling of a graph G = (V, E), where V denote the set of vertices and E denote the set of edges. f be the function where f : V → {1, - 1} with induced edge labeling f^* : E → {1, - 1} defined by f^* (xy) = f (x) f (y) is called a signed product cordial labeling if the difference between total number of vertices labeled by 1 and total number of vertices labeled by -1 is less than equal to 1, and the difference between total number of edges labeled by 1 and total number of edges labeled by -1 is less than equal to 1. i.e |v_f (1) - v_f (-1) |≤1 and $| e_{f}^{*} (1) - e_{f}^{*} (- 1) | \leq 1$ . f is called total signed product cordial labeling [22] if $| e_{f}^{*} (- 1) + v_{f} (- 1) - e_{f}^{*} (1) - v_{f} (1) | \leq 1$ , a graph which follow total signed product cordial labeling is known as total signed product graph.

Definition 2. Cartesian product of two graphs G = (V, E) and H = (V′, E′) is the Cartesian product between two set of vertices V (G) × V′ (G′) denoted by G × H, where (u, u′) and (v, v′) are the order pair of the Cartesian product will be adjacent in G × H if and only if either

u = v and u′ and v′ are adjacent in G′, or

u′ = v′ and u and v are adjacent in G.

Definition 3. A graph G is called a complete bipartite graph if its vertices can be partitioned into two subsets V₁ and V₂ such that no edges has both end points in the same subset, and each vertex of V₁ (V₂) is connected with all vertices of V₂ (V₁). Here V₁ = {X₁₁, X₁₂, . . . , X_1m} contains m vertices and V₂ = {Y₁₁, Y₁₂, . . . , Y_1n} contains n vertices.

A complete bipartite graph with |V₁| = m and |V₂| = n is denoted by K_m,n. A complete bipartite graph is called balanced bipartite graph when |V₁| = |V₂| = n and denoted by K_n,n.

According to the figure. 2, to draw the graph G = K_m,n × K_p,q, we consider p number of K_m,n at left and q number of K_m,n at right. To make it more clear we consider that left hand side contains X = {X₁, X₂, X₃, …, X_i, …, X_m} and Y = {Y₁, Y₂, Y₃, …, Y_i, …, Y_m} where X₁ = {x₁₁, x₁₂, x₁₃, …, x_1m}, X₂ = {x₂₁, x₂₂, x₂₃, …, x_2m}, and X_p = {x_p1, x_p2, x_p3, …, x_pm} and Y₁ = {y₁₁, y₁₂, y₁₃, …, y_1n}, Y₂ = {y₂₁, y₂₂, y₂₃, …, y_2n}, and Y_p = {y_p1, y_p2, y_p3, …, y_pn}. Right hand side contains U = {U₁, U₂, U₃, …, U_j, …, U_n} and V = {V₁, V₂, V₃, …, V_j, …, V_n} where U₁ = {u₁₁, u₁₂, u₁₃, …, u_1m}, U₂ = {u₂₁, u₂₂, u₂₃, …, u_2m}, and U_q = {u_q1, u_q2, u_q3, …, u_qm} and V₁ = {v₁₁, v₁₂, v₁₃, …, v_1n}, V₂ = {v₂₁, v₂₂, v₂₃, …, v_2n}, and V_q = {v_q1, v_q2, v_q3, …, v_qn}.

Lemma 1. lemma5 Let △ denote the maximum degree of the graph G = K_m,n × K_p,q, then $△ = {\begin{matrix} m + p & for m > n and p > q \\ m + q & for m > n and q > p \\ n + p & for n > m and p > q \\ n + q & for n > m and q > p \end{matrix}$ (1) Lemma 2. Total number of vertices in the graph G = K_m,n × K_p,q is (m + n + p + q)

Lemma 3. lemma1 Degree of each vertex in the graph G = K_n,n × K_n,n is 2n.

Lemma 4. lemma2 Total number vertices in the graph G = K_n,n × K_n,n is 4n²

Lemma 5. lemma3 Total number of edges in the graph G = K_n,n × K_n,n is 4n³

Lemma 6. lemma4 Graph G = K_n,n × K_n,n contains even number of vertices and edges for any n

3 Labeling of cartesian product between two balanced bipartite graph

In preliminaries section we have discussed about the graph obtained by Cartesian product between two complete bipartite graphs i.e G = K_m,n × K_p,q. To implement the labeling algorithmically we considered two balanced bipartite graph K_n,n,where each K_n,n contain two set of vertices X_i and Y_i for i = 1, 2, 3, . . . , n and |X_i| = |Y_i| = n where the vertices are connected according to the rule of balanced bipartite graph. The set X_i has n vertices and the vertices are X_i = {x_i1, x_i2, x_i3, . . . x_ip, . . . , x_in} similarly Y_i = {y_i1, y_i2, y_i3, . . . , y_ip, . . . , y_in}. Remaining already discussed in details in the preliminaries section.

3.1 Algorithm

To label the graph G = K _n,n × K_n,nby signed product and total signed product cordial labeling, we consider a matrix V_label [n²] [4] to store the vertex label having n² row and 4 column. In this algorithm we store the label in the matrix V_label because Vertex matrix V (K_n,n × K_n,n) mapped in the matrix V_label.

Algorithm 1 Vertex label algorithm of the graph G = K_n,n × K _n,n

1: Input: Graph G = K_n,n × K _n,n

2: Output:Vertex labelled graph G = K_n,n × K_n,n.

3: Initialization: V _label [n²] [4]

4: loop i = 1 to n ²

5: loop j = 1 to 4

6: loopj is odd then

7: V_label [i] [j] = -1

8: end if

9: if j is even then

10: V_label [i] [j] = -1

11: end if

12: end loop

13: end loop

3.1.1 The proof of correctness of the algorithm is given below

Theorem 1. Algorithm correctly label all the vertex of the graph K_n,n × K_n,n.

Proof 1. As we consider the graph G = K_n,n × K_n,n and the matrix V_label [n²] [4] to store the vertex label. According to the algorithm loop i will run upto n² times and for each encounter of loop i, j will run n times. For each encounter of loop j after checking when j is even put the label 1 and when j is odd put the label -1 to the matrix V_label [n²] [4]. Following this steps above algorithm successfully label the vertex of the graph G = K_n,n × K_n,n.

3.1.2 Time complexity of Algorithm

Algorithm used two loops, outer loop run upto n where as inner loop run upto 4 times for each encounter of outer loop. So time complexity of the algorithm is ○ (n²). $\begin{matrix} V_{label} [n^{2}] [4] \\ = (\begin{matrix} x_{11} & y_{11} & u_{11} & v_{11} \\ x_{12} & y_{12} & u_{12} & v_{12} \\ . . & . . & . . & . . \\ x_{1 n} & y_{1 n} & u_{1 n} & v_{1 n} \\ x_{21} & y_{21} & u_{21} & v_{21} \\ x_{22} & y_{22} & u_{22} & v_{22} \\ . . & . . & . . & . . \\ x_{2 n} & y_{2 n} & u_{2 n} & v_{2 n} \\ . . & . . & . . & . . \\ . . & . . & . . & . . \\ . . & . . & . . & . . \\ x_{n 1} & y_{n 1} & u_{n 1} & v_{n 1} \\ x_{n 2} & y_{n 2} & u_{n 2} & v_{n 2} \\ . . & . . & . . & . . \\ x_{nn} & y_{nn} & u_{nn} & v_{nn} \end{matrix}) = (\begin{matrix} - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ . . & . . & . . & . . \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ . . & . . & . . & . . \\ - 1 & 1 & - 1 & 1 \\ . . & . . & . . & . . \\ . . & . . & . . & . . \\ . . & . . & . . & . . \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ . . & . . & . . & . . \\ - 1 & 1 & - 1 & 1 \end{matrix}) \end{matrix}$

3.2 Algorithm

As it is clear that the graph G = K_n,n × K_n,n has two type of connection one is intra connection and other is inter connection. Intra connection means the connection of vertices within a balanced bipartite graph and inter connection means connection among the balanced bipartite graph (see Fig. 1). Here we present two algorithm of extracting edge labeling from the matrix V_label [n²] [4] one for intra connection and other for the inter connection edge.

Fig.1

K_m,n × K_p,q

Fig.2

Simplified Figure of K_m,n × K_p,q

To write the algorithm for extracting edge labeling from intra connection, we consider the matrix E_{each-copy-edge-label} [n] [n] to store the edge labeling and assume that vertex label of the each copy is stored in the matrix V_{each-copy-vertex-label} [n] [2]. Here we design the algorithm for a single copy of K_n,n. $\begin{matrix} V_{each - copy - vertex - label} [n] [2] \\ = (\begin{matrix} x_{11} & y_{11} \\ x_{12} & y_{12} \\ x_{13} & y_{13} \\ . . & . . \\ x_{1 n} & y_{1 n} \end{matrix}) = (\begin{matrix} - 1 & 1 \\ - 1 & 1 \\ - 1 & 1 \\ . . & . . \\ - 1 & 1 \end{matrix}) \end{matrix}$

Algorithm 2 Algorithm of extracting edge label matrix from intra connection vertices.

1: Input: The vertex label matrix V_{each-copy-vertex-label} [n] [2].

2: Output: Edge label matrix for intra connection vertices E_{each-copy-edge-label} [n] [n].

3: Initialization: E_{each-copy-edge-label} [n] [n],a,m

4: loap i = 1 to n

5: a = V_{each-copy-vertex-label} [i] [1].

6: loop j = 1 to n

7: m = a * V_{each-copy-vertex-label} [j] [2].

8: E_{each-copy-edge-label} [i] [j] = m.

9: end loop

10: end loop

3.2.1 The proof of correctness of the algorithm is given below

Theorem 2. Algorithm successfully extract edge labeling for intra connected vertices.

Proof 2. Considering the graph G = K_n,n × K_n,n and we already consider the vertex labeling of each copy as matrix V_{each-copy-vertex-label} [n] [2]. According to the algorithm for each copy of K_n,n we pick the first label that is a = V_{each-copy-vertex-label} [1] [1] and do multiply with each label of V_{each-copy-vertex-label} [i] [2], where i = 1, 2, 3, …, n and store the label in the matrix E_{each-copy-edge-label} [1] [j], where j = 1, 2, 3, …, n. Similarly we consider the second label that is a = V_{each-copy-vertex-label} [2] [1] and do multiply with each label of V_{each-copy-vertex-label} [i] [2], where i = 1, 2, 3, …, n and store the label in the matrix E_{each-copy-edge-label} [2] [j], where j = 1, 2, 3, …, n. Remaining steps are similar and we got the edge label matrix for intra connected vertices and all the elements are -1. The matrix is shown in details.

3.2.2 Time Complexity of Algorithm

Time complexity of the algorithm is ○ (n³), as here we have used three loops. We can see in the algorithm that one outer most loop k run 2n times and within this loop two more inner loops run here and both the loops run n times. $\begin{matrix} E_{each - copy - edge - label} [n] [n] \\ = (\begin{matrix} - 1 & - 1 & - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & - 1 & - 1 & . . . & - 1 \\ . . . & . . . & . . . & . . . & . . . & . . . \\ - 1 & - 1 & - 1 & - 1 & . . . & - 1 \end{matrix}) \end{matrix}$

As we have 2n copies of K_n,n in the graph G = K_n,n × K_n,n so the corresponding edge label matrix will be $\begin{matrix} ICM [n^{2}] [2 n] \\ = (\begin{matrix} (\begin{matrix} - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & . . . & - 1 \\ . . . & . . . & . . . & . . . \\ - 1 & - 1 & . . . & - 1 \end{matrix}) (\begin{matrix} - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & . . . & - 1 \\ . . . & . . . & . . . & . . . \\ - 1 & - 1 & . . . & - 1 \end{matrix}) \\ (\begin{matrix} - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & . . . & - 1 \\ . . . & . . . & . . . & . . . \\ - 1 & - 1 & . . . & - 1 \end{matrix}) (\begin{matrix} - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & . . . & - 1 \\ . . . & . . . & . . . & . . . \\ - 1 & - 1 & . . . & - 1 \end{matrix}) \\ . . . \\ (\begin{matrix} - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & . . . & - 1 \\ . . . & . . . & . . . & . . . \\ - 1 & - 1 & . . . & - 1 \end{matrix}) (\begin{matrix} - 1 & - 1 & . . . & - 1 \\ - 1 & - 1 & . . . & - 1 \\ . . . & . . . & . . . & . . . \\ - 1 & - 1 & . . . & - 1 \end{matrix}) \end{matrix}) \end{matrix}$

It is clear from the above matrix that all the elements of intra connected matrix is -1 and total number of elements are 2n³

3.3 Algorithm

Here we design the algorithm of extracting edge label from the inter connected vertices from the matrix V_label [n²] [4] and store it to the edge label matrix, which is ICM [n²] [2n]. To implement the algorithm we consider matrices MX_temp [n] [2] and MY_temp [n] [2] to store the each similar position label from each copy of either side copy of K_n,n. Similar position means we take each first element from each copy of K_n,n (see fig. 1) from set X of left and right side and stored it to MX_temp [n] [2] and from set Y of left and right side and stored it to MY_temp [n] [2] then pick second element from each copy similarly. So, for G = K_n,n × K_n,n we have n such copies of MX_temp [n] [2] and MY_temp [n] [2].

Algorithm 3 Algorithm of extracting edge label matrix from inter connected vertices

1: Input: Vertex label matrix V_label [n²] [4].

2: Output: Edge label matrix ICM [n²] [2n].

3: Initialization:ICM [n²] [2n].

4: Initialization: MX_temp [n] [2] , MY_temp [n] [2]

5: loop j = 1 to n

6: loop i = 1 to n

7: MX_temp [i] [1] = V_label [j + (i - 1) n] [1].

8: MX_temp [i] [2] = V_label [j + (i - 1) n] [3].

9: MY_temp [i] [1] = V_label [j + (i - 1) n] [2].

10: MY_temp [i] [2] = V_label [j + (i - 1) n] [4].

11: Call algorithm .

12: end loop.

13: end loop.

3.3.1 The proof of correctness of the algorithm 3 is given below

Theorem 3. Algorithm 3 successfully extract edge labeling for inter connected vertices.

Proof 3. Considering the graph G = K_n,n × K_n,n and we also consider two matrix MX_temp [n] [2] and MY_temp [n] [2] to store the elements of similar position from the matrix V_label [n²] [4]. According to the above algorithm for each encounter of loop j, i strike n times and each encounter of i stored each similar position element from the matrix V_label [n²] [4] to the matrices MX_temp [n] [2] and MY_temp [n] [2]. For each completion of loop i we call the algorithm for finding the edge label and stored it to the matrix ICM [n²] [2n]. As we have n copies of K_n,n in each side (see Fig. 1)that is why loop j runs n times to picking all the elements from the matrix V_label [n²] [4].

3.3.2 Time complexity of Algorithm 3

Time complexity of algorithm 3 is ○ (n²) as it contains one inner loop.

It is clear that all the elements of matrix MX_temp [n] [2] is -1 and MY_temp [n] [2] is 1. So, edge labeling matrix of such matrices always gives 1 as elements. Edge label matrix of inter connected vertices is shown in the matrix below. $\begin{matrix} E [n^{2}] [2 n] \\ = (\begin{matrix} (\begin{matrix} 1 & 1 & . . . & 1 \\ 1 & 1 & . . . & 1 \\ . . . & . . . & . . . & . . . \\ 1 & 1 & . . . & 1 \end{matrix}) (\begin{matrix} 1 & 1 & . . . & 1 \\ 1 & 1 & . . . & 1 \\ . . . & . . . & . . . & . . . \\ 1 & 1 & . . . & 1 \end{matrix}) \\ (\begin{matrix} 1 & 1 & . . . & 1 \\ 1 & 1 & . . . & 1 \\ . . . & . . . & . . . & . . . \\ 1 & 1 & . . . & 1 \end{matrix}) (\begin{matrix} 1 & 1 & . . . & 1 \\ 1 & 1 & . . . & 1 \\ . . . & . . . & . . . & . . . \\ 1 & 1 & . . . & 1 \end{matrix}) \\ . . . \\ (\begin{matrix} 1 & 1 & . . . & 1 \\ 1 & 1 & . . . & 1 \\ . . . & . . . & . . . & . . . \\ 1 & 1 & . . . & 1 \end{matrix}) (\begin{matrix} 1 & 1 & . . . & 1 \\ 1 & 1 & . . . & 1 \\ . . . & . . . & . . . & . . . \\ 1 & 1 & . . . & 1 \end{matrix}) \end{matrix}) \end{matrix}$

It is clear from the above matrix that all the elements of intra connected matrix is 1 and total number of elements are 2n³.

Theorem 4. The graph G = K_n,n × K_n,n signed product and total signed product cordial graph.

Proof 4. Let us consider the graph G = K_n,n × K_n,n, from lemma 2 and lemma lemma 3 we know that cardinality of vertex set and edge set are 4n² and 4n³ respectively. From algorithm we get that number of vertices label by -1 and number of vertices label by 1 is 2n² and 2n² respectively, i.e V_f (-1) = V_f (1) =2n². So |V_f (-1) - V_f (1) | = |2n² - 2n²|=0 ≤ 1. Now from the algorithm we can calculate the number of intra connected edges label by -1, which is 2n³ and also calculate the number of inter connected edges label by 1, which is 2n³ by the algorithm 3, i.e |e_{f
^*} (-1) - e_{f
^*} (1) | = |2n³ - 2n³|=0 ≤ 1, which comes under the limitation of signed product cordial labeling. Now |e_{f
^*} (-1) + v_f (-1) - e_{f
^*} (1) - v_f (1) | = |2n³ + 2n² - 2n³ - 2n²|=0 ≤ 1 follows the underlying rule of total signed product cordial labeling. Hence the proof.

3.4 Illustration

To demonstrate the above algorithms we consider a graph G = K_3,3 × K_3,3 (see the Fig. 3) for signed product and total signed product cordial labeling. From lemma 1 we know that degree of each vertex in the graph G = K_3,3 × K_3,3 is 6 and from lemma 2 it is also clear that total number vertices in the graph G = K_3,3 × K_3,3 is 36.

Fig.3

Cartesian product K_3,3 × K_3,3

For this graph G = K_3,3 × K_3,3 we consider the matrix V_label [9] [4]to store the vertex label matrix and by following the algorithm we got $V_{label} [9] [4] = (\begin{matrix} - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \\ - 1 & 1 & - 1 & 1 \end{matrix})$ We design the algorithm and algorithm 3 for extracting edge label from the vertex label matrix V_label [9] [4] for intra connected and inter connected vertices from the graph G = K_3,3 × K_3,3. Following matrices are. $\begin{matrix} Inter - CM [9] [6] \\ = (\begin{matrix} (\begin{matrix} - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \end{matrix}) (\begin{matrix} - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \end{matrix}) \\ (\begin{matrix} - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \end{matrix}) (\begin{matrix} - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \end{matrix}) \\ (\begin{matrix} - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \end{matrix}) (\begin{matrix} - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \\ - 1 & - 1 & - 1 \end{matrix}) \end{matrix}) \end{matrix}$

$E [9] [6] = (\begin{matrix} (\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}) (\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}) \\ (\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}) (\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}) \\ (\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}) (\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}) \\ ∥ \end{matrix})$

From the algorithm number of vertices label by -1 and number of vertices label by 1 both is equal to 18, i.e V_f (-1) = V_f (1) =18. So |V_f (-1) - V_f (1) | = |18 - 18|=0 ≤ 1. From Algorithm and algorithm 3 we can calculate the number of intra connected edges label by -1 and the number of inter connected edges label by 1 both is equal to 54. i.e |e_{f
^*} (-1) - e_{f
^*} (1) | = |54 - 54|=0 ≤ 1, which comes under the limitation of signed product cordial labeling. Now |e_{f
^*} (-1) + v_f (-1) - e_{f
^*} (1) - v_f (1) | = |54 + 18 - 54 - 18|=0 ≤ 1 follows the underlying rule of total signed product cordial labeling.

4 Conclusion

Graph labeling has many applications, where structure of graph simple or complex. In this article we considered a complex graph structure obtained by Cartesian product between two balanced bipartite and restructure the graph to make it simple. We have design one algorithm and it has been shown that the above said graph is signed product and total signed product cordial graph. We also design two algorithm one for extracting intra-connection edge labeling and other for extracting inter-connection edge labeling. Time complexity of the designed algorithm analysed and our algorithm worked successfully. This is the first attempt to consider such complex graph, so researchers can consider more complex graph and apply not only several part of cordial labeling but also all useful labeling technique. In future we want to work on the graph obtained by Cartesian product between two balanced bipartite graphs i.e G = Km, n × K_p,q and we also want to reconsider the time complexity of the each designed algorithms and try to reduce upto some optimum level.

Footnotes

Acknowledgement

The work is supported by the Department of Science and Technology, New Delhi, India, Ref. No. SB/S4/MS: 894/14.

References

Gallian

J.A.

, A dynamic survey of graph labeling, The Electronics Journal of Combinatorics 6 6(2010).

Griggs

and Yeh

R.K.

, Labeling graphs with a condition at distance two, SIAM J Discret Math 5 (1992)586–595.

Hegde

S.M.

, On Multiplicative Labelings of a Graph. Labeling of Discrete Structures and applications. Narosa Publishing House, (2008)83–96 New Delhi.

Beineke

L.W.

and Hegde

S.M.

, Strongly Multiplicative graphs, Discuss Math Graph Theory 21 (2001)63–75.

Cahit

, Cordial graphs a weaker version of graceful and harmonious graphs, Ars Combin 23 (1987)201–207.

Cahit

, On cordial and 3-equitable labellings of graphs, Util Math 37 (1990)189–198.

Cahit

, Status of graceful tree conjecture in 1989, in Topics in Combinatorics and Graph Theory. Bodendiek

and Henn

(eds), Physica-Verlag, Heidelberg, 1990.

Cahit

, Recent results and open problems on cordial graphs. Contemporary Methods in Graph Theory, Bodendiek

(ed.). Wissenschaftsverlag, Mannheim, (1990) pp. 209–230.

Cahit

, Equitable tree labellings, Ars Combin 40 (1995)279–286.

10.

Cahit

, On harmonious tree labellings, Ars Combin 41 (1995)311–317.

11.

Cahit

, H-cordial graphs, Bull Inst Combin Appl 18 (1996)87–101.

12.

Cahit

, Some totally modular cordial graphs, Discuss Math Graph Theory 22 (2002)247–258.

13.

Cahit

, Graceful labelings of rooted complete trees, Personal communication.

14.

Cahit

, A note on graceful directed trees, personal communication.

15.

Cahit

and Yilmaz

, E3-cordial graphs, Ars Combin 54 (2000)119–127.

16.

Graham

R.L.

and Sloane

N.J.A.

, On additive bases an harmonious graphs, SIAM J Algebr Disc Meth 1(4) (1980)382–404.

17.

Rosa

, On certain valuations of the vertices of a graph, Theory of graphs, International Symposium, 1967, 349–355.

18.

Babujee

J.B.

and Shobana

, Cordial languages and Cordial numbers, Journal of Applied Computer Science and Mathematics 13(6 (2012)), 9–12.

19.

Ulaganathan

P.P.

, Selvam

and Vijaya

K.P.

, Signed product cordial labeling in duplicate graphs of bistar, double star and triangular ladder graph, International Journal of Mathematics Trends and Technology (IJMTT) 33(1) (2016)19–24.

20.

Santhi

, Some star and bistar related signed product cordial graphs, International Journal of Mathematical Archive 6(10) (2015)232–236.

21.

Y.S.

, Lee

S.M.

and Shee

S.C.

, Cordial labelings of unicyclic graphs and generalized peterson graphs, Congr Numer 68 (1989)109–122.

22.

Santhi

and Kalidas

, Some graph operations on signed product cordial labeling graphs, International Journal of Mathematics Trends and Technology (IJMTT) 39(1) (2016)42–53.

23.

Vaidya

S.K.

and Shah

N.H.

, Cordial labeling for some bistar related graphs, International Journal of Mathematics and Soft Computing 4(2) (2014)33–39.

24.

Vaidya

S.K.

and Shah

N.H.

, Cordial labeling of snakes, International Journal of Mathematics And its Applications 2(3) (2014)17–27.

25.

Amanathulla

S.K.

and Pal

, Surjective L(2,1)-labeling of cycles and circular-arc graphs, Journal of Intelligent and Fuzzy Systems 35 (2018)739–748.

26.

Amanathulla

S.K.

, Sahoo

and Pal

, L(3,1,1)-labeling numbers of square of paths, complete graphs and complete bipartite graphs, Journal of Intelligent and Fuzzy Systems. DOI: 10.3233/JIFS-172195.