k -Zumkeller labeling of the Cartesian and tensor product of paths and cycles

Abstract

A k-Zumkeller labeling for the graph G = (V, E) is an assignment f of a label to each vertices of G such that each edge uv ∈ E is assigned the label f (u) f (v), the resulting edge labels are k distinct Zumkeller numbers. In this paper, we prove that the graph P_m × P_n is k-Zumkeller graph for m, n ≥ 3 while P_m × C_n and C_m × C_n are k-Zumkeller graphs for n ≡ 4 (mod2). Also we show that the graphs P_m ⊗ P_n and P_m ⊗ C_n for m, n ≥ 3 admit k-Zumkeller labeling. Further, the graph C_m ⊗ C_n where m or n is even admit a k-Zumkeller labeling.

Keywords

Zumkeller number Cartesian and tensor product of graphs 05C78

1 Introduction

Graph theory and its numerous operations have a vast number of implementations that are related to our real life to solve many problems. Rosenfeld’s fuzzy graph [1] allows one to make decisions in many fields of applications, including optimization, network routing, computer engineering, artificial intelligence, image segmentation, city planning, medical science, etc. For more details see the literature of Soumitra Poulik et al. [2 –5]. A fundamental aspect of a system is that its components are linked together to transmit data according to some pattern through physical communication links. Furthermore, there is no doubt that a system’s power is extremely dependent on the component connection pattern in the system. The system interconnection network, or network, is the connection pattern of the components in a system. Some schemes for the interconnection network are designed and some are borrowed from nature. For instance, some of the designed architectures include complete binary trees, butterflies and torus networks. For example, grids, hexagonal networks, honeycomb networks and diamond networks. They are referred to as natural architectures. The development of large-scale integrated circuit technology has allowed complex networks to be built. These networks are a powerful tool to describe and study the behavior of complex systems’ structural and dynamical aspects [6]. One of important method for modelling real networks, which generate a large graph out of two or more smaller ones. An apparent advantage of graph operations is the allowance of tractable analysis of the different characteristics of the resultant composite with graphs. Different graph products have been used in recent years to imitate real complex networks, including Cartesian product [7] and tensor (Kronecker, direct) product [8 –12].

All graphs in this paper are finite, simple, undirected and connected. For standard terminology and notation in graph theory we refer to Harary [13]. The concept of β-labeling of graph G = (V, E) introduced by Alex Rosa [14]. In 1972, the β-labeling was renamed graceful by S. W. Golomb [15] as it is known today. There is an enormous papers have been devoted to several kinds of labeling of graphs over the past three decades, which are updated by Gallian [11]. Labeled graphs are used in many areas of science and technology such as coding theory, mathematical modeling, x-ray, radar, circuit design, crystallography, radar and astronomy [16]. Also the graph labeling can be applied for automatic routing of data in the network and as efficient method to determine the time of communication in sensor network [17]. We begin with the definition of Zumkeller labeling and Zumkeller graphs.

Definition 1.1. [13] Let G = (V, E) be a graph. An injection function f : V → N is said to be a Zumkeller labeling of the graph G, if the induced function f^* : E → N defined as f^* (uv) = f (u) f (v) is a Zumkeller number for all uv ∈ E, u, v ∈ V. A graph that admits a Zumkeller labeling is called a Zumkeller graph.

The notion of Zumkeller labeling for graphs was introduced by Balamurugan et al. in [18]. The concept of Zumkeller labeling, strongly multiplicative Zumkeller labeling and cordial Zumkeller labeling of graphs have been introduced and studied in the literature [19 –24]. The concept of k-Zumkeller labeling of graphs has been introduced and investigated in [25, 26].

Definition 1.2. [25] A simple graph G is said to be a k-Zumkeller graph if the vertices of G can be labeled with distinct natural numbers such that the labels induced on the edges by multiplying the labels of ends vertices are k distinct Zumkeller numbers.

In [26], Balamurugan showed the path P_n is a 2-Zumkeller graph for all n ≥ 3 and the cycle C_n is a 3-Zumkeller graph iff n is even. We consider two types of graph products.

Definition 1.3. Let G₁ = (V₁, E₁) and G₂ = (V₂, E₂) be two graph. The Cartesian product G = G₁ × G₂ is the graph such that its vertex set $V (G) = {(u, \hat{u}) : u \in V (G_{1}), \hat{u} \in V (G_{2})}$ ; and any two vertices $(u_{1}, {\hat{u}}_{1})$ and $(u_{2}, {\hat{u}}_{2})$ are adjacent in G if and only if either u₁ = u₂ and ${\hat{u}}_{1}$ adjacent to ${\hat{u}}_{2}$ in G₂, or ${\hat{u}}_{1} = {\hat{u}}_{2}$ and u₁ adjacent to u₂ in G₁.

Definition 1.4. Let G₁ = (V₁, E₁) and G₂ = (V₂, E₂) be two graph. The tensor product G = G₁ ⊗ G₂, sometimes called the direct or Kronecker product is the graph such that its vertex set $V (G) = {(u, \hat{u}) : u \in V (G_{1}), \hat{u} \in V (G_{2})}$ ; and any two vertices $(u_{1}, {\hat{u}}_{1})$ and $(u_{2}, {\hat{u}}_{2})$ are adjacent in G if and only if u₁ adjacent to u₂ in G₁ and ${\hat{u}}_{1}$ adjacent to ${\hat{u}}_{2}$ in G₂.

The graph products are revealing of some aspects of network design. For example, if G specifies a PoP(point of presence)-level network topology, we can therefore create a simple router-level topology with redundant router pairs using a single edge G^* network and a Cartesian product [27]. Also the tensor Product is one of the most significant graph products with possible applications in engineering, computer science, and related fields. For example, the diagonal mesh investigated by Tang and Padubirdi [28] with regard to the multiprocessor network, is representative of a tensor product of two odd cycles that has several interesting properties. Among the different graphs products, the products that contain paths and cycles have proved to be one of the most significant [29]. For any real number x, define symbol ⌊x⌋ to represent the largest integer less than or equal to x and ⌈x⌉ to represent the smallest integer greater than or equal to x.

The main contribution of this paper is to study the k-Zumkeller labeling of the Cartesian and tensor product of paths and cycles.

2 Zumkeller numbers and their properties

In this section, we review the notations of Zumkeller numbers and some properties of Zumkeller numbers.

A positive integer n is called a perfect number if the sum of its proper positive factors equal n. Generalizing the concept of perfect numbers, Zumkeller published in Encyclopedia of Integer Sequences [30] A083207 a sequence of integers that their positive factors can be partitioned into two disjoint subsets with equal sum.

Definition 2.1. A positive integer n is called a Zumkeller number if the positive factors of n can be partitioned into two disjoint subsets such that the sums of the two subsets are equal.

We shall call a partition as a Zumkeller partition. 6, 12, 20, 24, 28, 30 are Zumkeller numbers.

Properties of Zumkeller Numbers

If the prime factorization of an even Zumkeller number n is $2^{k} p_{1}^{k_{1}} p_{2}^{k_{2}} . . . p_{m}^{k_{m}}$ . Then, at least one of k_i must be an odd number.

Let n be a Zumkeller number and p be a prime with (n, p) =1, then np^ℓ is a Zumkeller number for any positive integer ℓ.

If n is a Zumkeller number and $p_{1}^{k_{1}} p_{2}^{k_{2}} . . . p_{m}^{k_{m}}$ is the prime factorization of n. Then, for any positive integers ℓ₁, ℓ ₂, . . . , ℓ _m, $p_{1}^{k_{1} + ℓ_{1} (k_{1} + 1)} p_{2}^{k_{2} + ℓ_{2} (k_{2} + 1)} . . . p_{m}^{k_{m} + ℓ_{m} (k_{m} + 1)}$ is a Zumkeller number.

Let p ≠ 2 be a prime number and k be a positive integer with p ≤ 2^k+1 - 1. Then, 2^kp is a Zumkeller number.

3 Cartesian product and k-Zumkeller labeling

In this section, we prove that the Cartesian product P_m × P_n, P_m × C_n and C_m × C_n are k-Zumkeller graphs.

Theorem 3.1. Let m, n ≥ 3. The Cartesian product P_m × P_n is a 4-Zumkeller graph if n and m are odd, 5-Zumkeller graph otherwise.

Proof. Let G = P_m × P_n. Without loss of generality we suppose that n ≥ m. Let u₁, u₂, . . . , u_m and ${\hat{u}}_{1}, {\hat{u}}_{2}, . . ., {\hat{u}}_{n}$ be the vertices of the paths P_m and P_n respectively. Thus vertex set of G is $V (G) = {v_{ij} = (u_{i}, {\hat{u}}_{j}) : 1 \leq i \leq m, 1 \leq j \leq n}$ and edge set is $E (G) = {e_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i}, {\hat{u}}_{j + 1}) : 1 \leq i \leq m, 1 \leq j \leq n - 1} ⋃ {{\hat{e}}_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i + 1}, {\hat{u}}_{j}) : 1 \leq i \leq m - 1, 1 \leq j \leq n}$ . Further, we observe that the graph G has mn vertices and 2mn - (m + n) edges. Now we define a vertex function f : V (G) → N as follows:

For 1 ≤ i ≤ m, 1 ≤ i ≤ n.

$\begin{matrix} f (v_{ij}) = {\begin{matrix} 2^{\frac{1}{2} (j + 1) + \frac{n}{2} (i - 1)}, & if i is odd, j is odd \\ p 2^{⌊ \frac{mn}{2} ⌋ - \frac{1}{2} j - \frac{n}{2} (i - 1)}, & if i is odd, j is even \\ p 2^{⌊ \frac{mn}{2} ⌋ - ⌊ \frac{n}{2} ⌋ - \frac{1}{2} (j + 1) - \frac{n}{2} (i - 2)}, & if i is even, j is odd \\ 2^{⌈ \frac{n}{2} ⌉ + \frac{1}{2} j + \frac{n}{2} (i - 2)}, & if i is even, j is even . \end{matrix} \end{matrix}$

Where p < 10, p ≠ 2 is a prime number. Hence the labels of the edges of G are given as follows:

$\begin{matrix} f^{*} (v_{ij} v_{i (j + 1)}) \\ = {\begin{matrix} p 2^{⌊ \frac{mn}{2} ⌋}, & if i is odd, j is odd \\ p 2^{⌊ \frac{mn}{2} ⌋ + 1}, & if i is odd, j is even \\ p 2^{⌊ \frac{mn}{2} ⌋ - ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{2} ⌉}, & if i is even, j is odd \\ p 2^{⌊ \frac{mn}{2} ⌋ - ⌊ \frac{n}{2} ⌋ + ⌈ \frac{n}{2} ⌉ - 1}, & if i is even, j is even . \end{matrix} \end{matrix}$ (1)

$\begin{matrix} f^{*} (v_{ij} v_{(i + 1) j}) \\ = {\begin{matrix} p 2^{⌊ \frac{mn}{2} ⌋ - ⌊ \frac{n}{2} ⌋}, if i is odd, j is odd \\ p 2^{⌊ \frac{mn}{2} ⌋ - ⌊ \frac{n}{2} ⌋ + n}, if i is even, j is odd \\ p 2^{⌊ \frac{mn}{2} ⌋ + ⌈ \frac{n}{2} ⌉}, if i is odd, j is even \\ p 2^{⌊ \frac{mn}{2} ⌋ + ⌈ \frac{n}{2} ⌉ - n}, if i is even, j is even . \end{matrix} \end{matrix}$ (2)Case(i). When n and m are odd.

In this case the equations (1), (2) become:

$\begin{matrix} f^{*} (v_{ij} v_{i (j + 1)}) = {\begin{matrix} p 2^{⌊ \frac{mn}{2} ⌋}, if i is odd, j is odd \\ p 2^{⌊ \frac{mn}{2} ⌋ + 1}, if i is odd, j is even \\ p 2^{⌊ \frac{mn}{2} ⌋ + 1}, if i is even, j is odd \\ p 2^{⌊ \frac{mn}{2} ⌋}, if i is even, j is even . \end{matrix} \end{matrix}$ $\begin{matrix} f^{*} (v_{ij} v_{(i + 1) j}) = {\begin{matrix} p 2^{\frac{mn}{2} - \frac{n - 1}{2}}, if i is odd, j is odd \\ p 2^{\frac{mn}{2} + \frac{n + 1}{2}}, if i is odd, j is even \\ p 2^{\frac{mn}{2} + \frac{n + 1}{2}}, if i is even, j is odd \\ p 2^{\frac{mn}{2} - \frac{n - 1}{2}}, if i is even, j is even . \end{matrix} \end{matrix}$

One can observe that the edges of G receive only 4 distinct Zumkeller numbers $p 2^{\frac{mn}{2}}, p 2^{\frac{mn}{2} + 1}, p 2^{\frac{mn}{2} - \frac{n - 1}{2}}$ and $p 2^{\frac{mn}{2} + \frac{n + 1}{2}}$ . Therefore G is a 4-Zumkeller graph.

Case(ii). Otherwise.

In this case the equations (1), (2) become:

$\begin{matrix} f^{*} (v_{ij} v_{i (j + 1)}) = {\begin{matrix} p 2^{\frac{mn}{2}}, if i is odd, j is odd \\ p 2^{\frac{mn}{2} + 1}, if i is odd, j is even \\ p 2^{\frac{mn}{2}}, if i is even, j is odd \\ p 2^{\frac{mn}{2} - 1}, if i is even, j is even . \end{matrix} \end{matrix}$ $\begin{matrix} f^{*} (v_{ij} v_{(i + 1) j}) = {\begin{matrix} p 2^{\frac{mn}{2} - \frac{n}{2}}, if i is odd, j is odd \\ p 2^{\frac{mn}{2} + \frac{n}{2}}, if i is odd, j is even \\ p 2^{\frac{mn}{2} + \frac{n}{2}}, if i is even, j is odd \\ p 2^{\frac{mn}{2} - \frac{n}{2}}, if i is even, j is even . \end{matrix} \end{matrix}$

It obvious that the edges of G receive only 5 distinct Zumkeller numbers $p 2^{\frac{mn}{2}}, p 2^{\frac{mn}{2} + 1}, p 2^{\frac{mn}{2} - 1}, p 2^{\frac{mn}{2} - \frac{n - 1}{2}}$ and $p 2^{\frac{mn}{2} + \frac{n + 1}{2}}$ . Hence G is a 5-Zumkeller graph.

Example 3.1. Figure 1 illustrates a 4-Zumkeller labeling of the Cartesian product P_m × P_n, where m = 5 and n = 9.

Fig. 1

4-Zumkeller labeling of P₅ × P₉.

Example 3.2. Figure 2 illustrates a 5-Zumkeller labeling of the Cartesian product P_m × P_n, where m = n = 6.

Fig. 2

5-Zumkeller labeling of P₆ × P₆.

Theorem 3.2. Let m ≥ 3. The Cartesian product P_m × C_n is a 7-Zumkeller graph when n ≡ 6 (mod 2), 5-Zumkeller graph when n = 4.

Proof. Let G = P_m × C_n. Let u₁, u₂, . . . , u_m and ${\hat{u}}_{1}, {\hat{u}}_{2}, . . ., {\hat{u}}_{n}$ , n ≡ 4 (mod 2) be the vertices of the path P_m and cycle C_n respectively. Thus vertex set of G is $V (G) = {v_{ij} = (u_{i}, {\hat{u}}_{j}) : 1 \leq i \leq m, 1 \leq j \leq n}$ and edge set is $E (G) = {e_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i}, {\hat{u}}_{j + 1}) : 1 \leq i \leq m, 1 \leq j \leq n - 1} ⋃ {{\hat{e}}_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i + 1}, {\hat{u}}_{j}) : 1 \leq i \leq m - 1, 1 \leq j \leq n} ⋃ {e_{in} = (u_{i}, {\hat{u}}_{n}) (u_{i}, {\hat{u}}_{1}) : 1 \leq i \leq m}$ . Hence G has mn vertices and 2mn - n edges. We can define f : V (G) → N as follows:$ For 1 ≤ i ≤ m, 1 ≤ j ≤ n $\begin{matrix} f (v_{ij}) \\ = {\begin{matrix} 2^{\frac{1}{2} (j + 1) + \frac{n}{2} (i - 1)}, if i is odd, j is odd \\ p 2^{\frac{mn}{2} - \frac{1}{2} j - \frac{n}{2} (i - 1)}, if i is odd, j is even \\ p 2^{\frac{n (m - 1)}{2} - \frac{1}{2} (j + 1) - \frac{n}{2} (i - 2)}, if i is even, j is odd \\ 2^{\frac{n}{2} + \frac{1}{2} j + \frac{n}{2} (i - 2)}, if i is even, j is even . \end{matrix} \end{matrix}$

Where p < 10, p ≠ 2 is a prime number. Then the labels of the edges of G are given as follows:

Case (i): When n ≡ 6 (mod 2)

For 1 ≤ j ≤ n - 1.

$f^{*} (v_{ij} v_{i (j + 1)}) = {\begin{matrix} p 2^{\frac{mn}{2}}, if i is odd, j is odd \\ p 2^{\frac{mn}{2} + 1}, if i is odd, j is even \\ p 2^{\frac{mn}{2}}, if i is even, j is odd \\ p 2^{\frac{mn}{2} - 1}, if i is even, j is even . \end{matrix}$ (3)

For 1 ≤ i ≤ m - 1.

$f^{*} (v_{ij} v_{(i + 1) j}) = {\begin{matrix} p 2^{\frac{n (m - 1)}{2}}, if i is odd, j is odd \\ p 2^{\frac{n (m + 1)}{2}}, if i is odd, j is even \\ p 2^{\frac{n (m + 1)}{2}}, if i is even, j is odd \\ p 2^{\frac{n (m - 1)}{2}}, if i is even, j is even . \end{matrix}$ (4)

$f^{*} (v_{in} v_{i 1}) = {\begin{matrix} p 2^{\frac{n (m - 1)}{2} + 1}, if i is odd \\ p 2^{\frac{n (m + 1)}{2} - 1}, if i is even . \end{matrix}$ (5) From equations (3) to (5), we observe that the edges of G receive only 7 distinct Zumkeller numbers $p 2^{\frac{mn}{2}}$ , $p 2^{\frac{mn}{2} + 1}$ , $p 2^{\frac{mn}{2} - 1}$ , $p 2^{\frac{n (m - 1)}{2}}$ , $p 2^{\frac{n (m + 1)}{2}}$ , $p 2^{\frac{n (m - 1)}{2} + 1}$ and $p 2^{\frac{n (m + 1)}{2} - 1}$ . Hence G is a 7-Zumkeller graph.

Case (ii): When n = 4.

In this case, the edge label of the edges of G are given as follows:

For 1 ≤ j ≤ 3.

$f^{*} (v_{ij} v_{i (j + 1)}) = {\begin{matrix} p 2^{2 m}, if i is odd, j is odd \\ p 2^{2 m + 1}, if i is odd, j is even \\ p 2^{2 m}, if i is even, j is odd \\ p 2^{2 m - 1}, if i is even, j is even . \end{matrix}$ (6)

For 1 ≤ i ≤ 4.

$f^{*} (v_{ij} v_{(i + 1) j}) = {\begin{matrix} p 2^{2 m - 2}, if i is odd, j is odd \\ p 2^{2 m + 2}, if i is odd, j is even \\ p 2^{2 m + 2}, if i is even, j is odd \\ p 2^{2 m - 2}, if i is even, j is even . \end{matrix}$ (7)

$f^{*} (v_{i 4} v_{i 1}) = {\begin{matrix} p 2^{2 m - 1}, if i is odd \\ p 2^{2 m + 1}, if i is even . \end{matrix}$ (8) From equations (6) to (8), we note that the edges of G receive only 5 distinct Zumkeller numbers p2^2m, p2^2m-1, p2^2m+1, p2^2m+2 and p2^2m-2. Hence G is a 5-Zumkeller graph.□

Example 3.3. Figures 3 and 4 illustrate 7-Zumkeller labeling and 5-Zumkeller labeling of the Cartesian product P_m × C_n respectively, where {m = 5, n = 8} and {m = 5, n = 4}.

Fig. 3

7-Zumkeller labeling of P₅ × C₈.

Fig. 4

5-Zumkeller labeling of P₅ × C₄.

Theorem 3.3. Let m, n ≡ 4 (mod 2). The Cartesian product C_m × C_n is a 9-Zumkeller graph, when m,n ≡ 6 (mod 2), 7-Zumkeller graph otherwise.

Proof. Let G = C_m × C_n. Let u₁, u₂, . . . , u_m and ${\hat{u}}_{1}, {\hat{u}}_{2}, . . ., {\hat{u}}_{n}$ , be the vertices of the even cycles C_m, C_n respectively. Then vertex set of G is $V (G) = {v_{ij} = (u_{i}, {\hat{u}}_{j}) : 1 \leq i \leq m, 1 \leq j \leq n}$ and edge set is $E (G) = {e_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i}, {\hat{u}}_{j + 1}) : 1 \leq i \leq m, 1 \leq j \leq n - 1} ⋃ {{\hat{e}}_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i + 1}, {\hat{u}}_{j}) : 1 \leq i \leq m - 1$ , $1 \leq j \leq n} ⋃ {e_{in} = (u_{i}, {\hat{u}}_{n}) (u_{i}, {\hat{u}}_{1}) : 1 \leq i \leq m} ⋃ {{\hat{e}}_{mj} = (u_{1}, {\hat{u}}_{j}) (u_{m}, {\hat{u}}_{j}) : 1 \leq j \leq n}$ . So G has mn vertices and 2mn edges. We define the vertex function labeling f : V (G) → N as in the Theorem 3.4. Moreover, the edges $e_{ij}, {\hat{e}}_{ij}$ and e_in receive 7 Zumkeller number when m,n ≡ 6 (mod 2), 5 Zumkeller number when m or n equal 4. The labels of the edges ${\hat{e}}_{mj} = (u_{1}, {\hat{u}}_{j}) (u_{m}, {\hat{u}}_{j}), 1 \leq j \leq n$ are given as follows:

For 1 ≤ j ≤ n. $\begin{matrix} f^{*} (v_{1 j} v_{mj}) = {\begin{matrix} p 2^{\frac{n}{2}}, if j is odd \\ p 2^{mn - \frac{n}{2}}, if j is even \end{matrix} \end{matrix}$ Where p < 10, p ≠ 2 is a prime number. Thus the edges of G receive only 9 distinct Zumkeller numbers when m,n ≡ 6 (mod 2), 7 distinct Zumkeller number when m or n equal 4.

Example 3.4. Figures 5 and 6 illustrate 9-Zumkeller labeling and 7-Zumkeller labeling of the Cartesian product C_m × C_n respectively, where {m = 6, n = 8} and {m = 6, n = 4}.

Fig. 5

9-Zumkeller labeling of C₆ × C₈.

Fig. 6

7-Zumkeller labeling of C₆ × C₄.

4 Tensor product and k-Zumkeller labeling

In this section, we prove that the tensor product P_m ⊗ P_n, P_m ⊗ C_n and C_m ⊗ C_n are k-Zumkeller graphs.

Theorem 4.1. The tensor product P_m ⊗ P_n is a 4-Zumkeller graph for all m, n ≥ 3.

Proof. Let {u₁, u₂, . . . , u_m} and { ${\hat{u}}_{1}, {\hat{u}}_{2}, . . ., {\hat{u}}_{n}$ } denote the vertex sets of two paths P_m, P_n respectively. Let G = P_m ⊗ P_n. Then the vertex set of G is $V (G) = {v_{ij} = (u_{i}, {\hat{u}}_{j}) : 1 \leq i \leq m, 1 \leq j \leq n}$ and edge set is $E (G) = {e_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i + 1}, {\hat{u}}_{j + 1}) : 1 \leq i \leq m - 1, 1 \leq j \leq n - 1}$ ∪ ${{\hat{e}}_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i + 1}, {\hat{u}}_{j - 1}) : 2 \leq i \leq m - 1, 1 \leq j \leq n}$ . It is clear that G has mn vertices and 2 (m - 1) (n - 1) edges. Now we define labeling f : V (G) → N as follows:

For 1 ≤ i ≤ m, 1 ≤ j ≤ n. $\begin{matrix} f (v_{ij}) = {\begin{matrix} 2^{\frac{n}{2} (i - 1) + j}, i is odd \\ p 2^{n ⌊ \frac{m}{2} ⌋ - \frac{n}{2} (i - 2) - j}, i is even . \end{matrix} \end{matrix}$ Where p is a prime number greater than 2 but less than 10. Therefore the labels of the edges of G are given as follows:

For 1 ≤ i ≤ m - 1, 1 ≤ j ≤ n - 1.

$f^{*} (v_{ij} v_{(i + 1) (j + 1)}) = {\begin{matrix} p 2^{n ⌊ \frac{m}{2} ⌋ - 1}, i is odd \\ p 2^{n ⌊ \frac{m}{2} ⌋ + n + 1}, i is even . \end{matrix}$ (9) For 1 ≤ i ≤ m - 1, 2 ≤ j ≤ n.

$f^{*} (v_{ij} v_{(i + 1) (j - 1)}) = {\begin{matrix} p 2^{n ⌊ \frac{m}{2} ⌋ + 1}, i is odd \\ p 2^{n ⌊ \frac{m}{2} ⌋ + n - 1}, i is even . \end{matrix}$ (10) From equations (9), (10), it is observed that the edges of G receive only 4 distinct Zumkeller numbers $p 2^{n ⌊ \frac{m}{2} ⌋ - 1}$ , $p 2^{n ⌊ \frac{m}{2} ⌋ + n + 1}$ , $p 2^{n ⌊ \frac{m}{2} ⌋ + 1}$ and $p 2^{n ⌊ \frac{m}{2} ⌋ + n - 1}$ . Thus G is a 4-Zumkeller graph.□

Example 4.1. Figure 7 illustrates a 4-Zumkeller labeling of the tensor product P_m ⊗ P_n, where m = 5 and n = 7.

Fig. 7

4-Zumkeller labeling of P₅ ⊗ P₇.

Theorem 4.2. The tensor product P₂ ⊗ P_n is a 2-Zumkeller graph for all n.

Proof. Let G = P₂ ⊗ P_n. Then the vertex set of G is $V (G) = {v_{ij} = (u_{i}, {\hat{u}}_{j}) : 1 \leq i \leq 2, 1 \leq j \leq n}$ and edge set is $E (G) = {e_{1 j} = (u_{1}, {\hat{u}}_{j}) (u_{2}, {\hat{u}}_{j + 1}) : 1 \leq j \leq n - 1} \cup {{\hat{e}}_{1 j} = (u_{1}, {\hat{u}}_{j}) (u_{2}, {\hat{u}}_{j - 1}) : 2 \leq j \leq n}$ . It is clear that G has 2n vertices and 2 (n - 1) edges. Now we define labeling f : V (G) → N as follows:

For 1 ≤ j ≤ n. $\begin{matrix} f (v_{1 j}) = {\begin{matrix} 2^{\frac{j + 1}{2}} j is odd \\ 2^{n - \frac{j}{2} + 1}, j is even . \end{matrix} \end{matrix}$ $\begin{matrix} f (v_{2 j}) = {\begin{matrix} p 2^{\frac{j - 1}{2}} j is odd \\ p 2^{n - \frac{j}{2}}, j is even . \end{matrix} \end{matrix}$ Where p is a prime number greater than 2 but less than 10. Further, the labels of the edges of G are given as follows:

For 1 ≤ j ≤ n - 1.

$f^{*} (v_{1 j} v_{2 (j + 1)}) = {\begin{matrix} p 2^{n} j is odd \\ p 2^{n + 1}, j is even . \end{matrix}$ (11) For 2 ≤ j ≤ n.

$f^{*} (v_{1 j} v_{2 (j - 1)}) = {\begin{matrix} p 2^{n + 1} j is odd \\ p 2^{n}, j is even . \end{matrix}$ (12) From equations (11), (12), it is clear that the edges of G receive only 2 distinct Zumkeller numbers p2ⁿ and p2ⁿ⁺¹. Then G is a 2-Zumkeller graph.

Example 4.2. Figure 8 illustrates a 2-Zumkeller labeling of the tensor product P_m ⊗ P_n, where m = 2 and n = 7.

Fig. 8

2-Zumkeller labeling of P₂ ⊗ P₇.

Theorem 4.3. The tensor product P_m ⊗ C_n is a 6-Zumkeller graph for all m, n ≥ 3.

Proof. Let P_m be the path of length m - 1, C_n be the cycle of length n and let G be the graph obtained by tensor product of P_m and C_n. Then the vertex set of G is $V (G) = {v_{ij} = (u_{i}, {\hat{u}}_{j}) : 1 \leq i \leq m, 1 \leq j \leq n}$ and edge set is $E (G) = {e_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i + 1}, {\hat{u}}_{j + 1}) : 1 \leq i \leq m - 1, 1 \leq j \leq n - 1} \cup {{\hat{e}}_{ij} = (u_{i}, {\hat{u}}_{j}) (u_{i + 1}, {\hat{u}}_{j - 1}) : 1 \leq i \leq m - 1, 2 \leq j \leq n} \cup {e_{in} = (u_{i}, {\hat{u}}_{1}) (u_{i + 1}, {\hat{u}}_{n}) : 1 \leq i \leq m - 1} \cup {{\hat{e}}_{in} = (u_{i}, {\hat{u}}_{n}) (u_{i + 1}, {\hat{u}}_{1}) : 1 \leq i \leq m - 1}$ . Then, it obvious that the graph G = P_m ⊗ C_n has mn vertices and 2m (n - 1) edges. The labels of vertices v_ij for 1 ≤ i ≤ m, 1 ≤ j ≤ n are given as in Theorem 4.1. Then the label of the edges f^* (v_ijv_(i+1)(j+1))(1 ≤ i ≤ m - 1, 1 ≤ j ≤ n - 1) and f^* (v_ijv_(i+1)(j-1)), (1 ≤ i ≤ m - 1, 2 ≤ j ≤ n) receive only 4 distinct Zumkeller numbers. The labels of the edges $e_{in}, {\hat{e}}_{in}, 1 \leq i \leq m - 1$ are given as follows:

$f^{*} (v_{i 1} v_{(i + 1) n}) = {\begin{matrix} p 2^{n ⌊ \frac{m}{2} ⌋ - n + 1}, i is odd \\ p 2^{n ⌊ \frac{m}{2} ⌋ + 2 n - 1}, i is even . \end{matrix}$ (13)

$f^{*} (v_{in} v_{(i + 1) 1}) = {\begin{matrix} p 2^{n ⌊ \frac{m}{2} ⌋ + n - 1}, i is odd \\ p 2^{n ⌊ \frac{m}{2} ⌋ + 1}, i is even . \end{matrix}$ (14) Where p < 10, p ≠ 2 is a prime number. From equations (9), (10), (13) and (14), it is noticed that the edges of G receive only 6 distinct Zumkeller numbers $p 2^{n ⌊ \frac{m}{2} ⌋ - 1}$ , $p 2^{n ⌊ \frac{m}{2} ⌋ + n + 1}$ , $p 2^{n ⌊ \frac{m}{2} ⌋ + 1}$ , $p 2^{n ⌊ \frac{m}{2} ⌋ + n - 1}$ , $p 2^{n ⌊ \frac{m}{2} ⌋ - n + 1}$ and $p 2^{n ⌊ \frac{m}{2} ⌋ + 2 n - 1}$ . Hence G graph is a 6-Zumkeller labeling.□

Example 4.3. Figure 9 illustrates a 6-Zumkeller labeling of the tensor product P_m ⊗ C_n, where m = 5 and n = 6.

Fig. 9

6-Zumkeller labeling of P₅ ⊗ C₆.

Theorem 4.4. Let m, n ≥ 3. The tensor product C_m ⊗ C_n is a 8-Zumkeller graph, where m or n is even.

Proof. Without loss of generality we may assume that m is even. By joining the vertices v_1j, v_m(j+1),1 ≤ i ≤ n and v_1j, v_m(j-1), 2 ≤ j ≤ n of the graph C_m ⊗ P_n in the Theorem 4.5. with additional edges we get the tensor product of the two cycles C_m, C_n. Thus, G = C_m ⊗ C_n. The labels of vertices v_ij for 1 ≤ i ≤ m, 1 ≤ j ≤ n are given as in Theorem 4.5. and the labels of the edges f^* (v_ijv_(i+1)(j+1))(1 ≤ i ≤ m - 1, 1 ≤ j ≤ n - 1), f^* (v_ijv_(i+1)(j-1)), f^* (v_i1v_(i+1)n) and f^* (v_inv_(i+1)1) (1 ≤ i ≤ m - 1, 2 ≤ j ≤ n) receive only 6 distinct Zumkeller numbers and the labels of the additional edges v_1j, v_m(j+1), 1 ≤ j ≤ n - 1 and v_1j, v_m(j-1), 2 ≤ j ≤ n are given as follows: $f^{*} (v_{1 j}, v_{m (j + 1)}) = p 2^{n - 1}, 1 \leq j \leq n - 1$ (15) $f^{*} (v_{1 j}, v_{m (j - 1)}) = p 2^{n + 1}, 2 \leq j \leq n .$ (16) Where p is a prime number greater than 2 but less than 10. From Equations (9), (10), (13), (14), (15) and (16). It is observed that the edges of G receive only 8 distinct Zumkeller numbers $p 2^{\frac{mn}{2} - 1}$ , $p 2^{\frac{mn}{2} + n + 1}$ , $p 2^{\frac{mn}{2} + 1}$ , $p 2^{\frac{mn}{2} + n - 1}$ , $p 2^{\frac{mn}{2} - n - 1}$ , $p 2^{\frac{mn}{2} + 2 n - 1}$ , p2^n-1 and p2ⁿ⁺¹. Thus G is a 8-Zumkeller graph.

Example 4.4. Figure 10 illustrates a 8-Zumkeller labeling of the tensor product C_m ⊗ C_n, where m = 4 and n = 6.

Fig. 10

8-Zumkeller labeling of C₄ ⊗ C₆.

5 Applications

Appropriate labeling on the graph can be applied based on the problem. Therefore labeled graphs are becoming an ever more popular family of Mathematical Models for a wide range of applications. In the following We’ll list some of the graph labeling applications [31 –42].

Qualitative labeling of graphic elements has motivated work in various fields of human enquiry such as social psychology conflict resolution, electrical circuit theory, and energy crisis.

The graph labeling applied in, coding theory by designing certain important classes of good non-periodic pulse radar and missile guidance codes is equivalent to labeling the entire graph so that all edge labels are distinct. The labels of nodes then determine the time positions in which the pulses are transmitted.

The x-ray crystallography: X-ray diffraction is one of the most effective methods used to describe the structural properties of crystalline solids, in which an X-ray beam hits a crystal and diffracts in many specific directions. In some cases, more than one structure holds the same knowledge regarding diffraction. This problem is mathematically equivalent to evaluating the labeling of the corresponding graphs generating a given set of edge labels.

In the communication: graph labeling is used to assign a channel to each station in order to avoid interference. Also, problems with mobile Adhoc networks (MANETS) can be solved by using it.

Graph labeling helped to provide a system for identifying human faces from individual images, from a large database containing one photo for each person.

The graph labeling plays a vital important role in chemistry that we can represent and analyze the chemical reaction by labeled graphs.

6 Conclusion

Undoubtedly a lot of networks in the nature can be described by using graph products which allow the mathematical design of a network in small terms of subgraphs. In the forgoing sections, we studied the k-Zumkeller labeling of the Cartesian and tensor product of the paths and cycles. We show that for m, n ≥ 3 the graph P_m × P_n is a k-Zumkeller graph, while P_m × C_n and C_m × C_n admit k-Zumkeller labeling for m ≡ 4 (mod 2). In the second part of the paper we prove that the graphs P_m ⊗ P_n and P_m ⊗ C_n for m, n ≥ 3 are k-Zumkeller graphs. Moreover, we show that C_m ⊗ C_n where m or n is even admit a k-Zumkeller labeling. According to obtained results, we suggest the following open problem.

Open problem:

In future we want to study the k-Zumkeller labeling of the graph obtained by Strong and Lexicographic product of paths and cycles.

References

R.A. Fuzzy graphs, Zadeh

L.A.

, et al. (Eds.), Fuzzy Sets and Their Applications to Cognitive and Decision Processes, Academic Press, Berlin/New York (1975), pp. 75–95.

Poulik

and Ghorai

, Detour g-interior nodes and detour g-boundary nodes in bipolar fuzzy graph with applications, Hacettepe Journal of Mathematics and Statistics 49(1), 106–119.

Poulik

and Ghorai

, Certain indices of graphs under bipolar fuzzy environment with applications, Soft Computing 24(7), 5119–5131.

Poulik

and Ghorai

, Note on Bipolar fuzzy graphs with applications, Knowledge-Based Systems 192, 1–5.

Poulik

, Ghorai

and Xin

, Pragmatic results in Taiwan education system based IVFG & IVNG, Soft Comput (2020), https://doi.org/10.1007/s00500-020-05180-4.

Newman

M.E.

, The structure and function of complex networks, SIAM Rev 45(2) (2003), 167–256.

Imrich

and Klavzar

, Product graphs: Structure and Recognition, Wiley (2000).

Weichsel

P.M.

, The Kronecker product of graphs, Proc Am Math Soc 13 (1962), 47–52.

Leskovec

and Faloutsos

, Scalable modeling of real graphs using Kronecker multiplication, in Proceedings of the 24th International Conference on Machine Learning. New York, NY, USA: ACM, 20–24 (2007), 497–504.

10.

Mahdian

and Xu

, Stochastic Kronecker graphs, in, Proceedings of the 5th International Conference on Algorithms and Models for the Web-Graph. San Diego, CA: Springer-Verlag, Berlin 11-12 (2007), 453–466.

11.

Leskovec

, Chakrabarti

, Kleinberg

, Faloutsos

and Ghahramani

, Kronecker graphs: An approach to modeling networks, J Mach Learn Res 11 (2010), 985–1042.

12.

Mahdian

and Xu

, Stochastic Kronecker graphs, Random Struct Algorithms 38(4) (2011), 453–466.

13.

Harary

, Graph Theory, Addison-wesley, Reading Mass, (1972).

14.

Rosa

, On certain valuations of the vertices of a graph, Theory of graphs (Internat. symposium, Rome, July 1966), Gordon and Breach, New York, (1967), 349–355.

15.

Golomb

, How to number a graph, Graph theory and computing, R. C. Reading, ed., Academic Press, New York, (1972), 23–37.

16.

Gallian

J.A.

, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics, Twentieth edition, December 22, (2017), #DS6.

17.

Vinutha

M.S.

and Arathi

, Applications of Graph Coloring and Labeling in Computer Science, International Journal on Future Revolution in Computer Science & Communication Engineering 3(8) (2017).

18.

Balamurugan

B.J.

, Thirusangu

and Thomas

D.G.

, Zumkeller labeling of some cycle related graphs. In: Proceedings of International Conference on Mathematical Sciences (ICMS|2014), Elsevier, (2014), 549–553.

19.

Balamurugan

B.J.

, Thirusangu

and Thomas

D.G.

, Zumkeller labeling algorithms for complete bipartite graphs and wheel graphs, Advances in Intelligent Systems and Computing, Springer 324 (2015), 405–413.

20.

Balamurugan

B.J.

, Thirusangu

and Thomas

D.G.

, Algorithms for Zumkeller labeling of full binary trees and square grids, Advances in Intelligent Systems and Computing, Springer 325 (2015), 183–192.

21.

Balamurugan

B.J.

, Thirusangu

, Thomas

D.G.

, Strongly multiplicative Zumkeller labeling for acyclic graphs, In: Proceedings of International Conference on Emerging Trends in Science, Engineering, Business and Disaster Management (ICBDM - 2014), to appear in IEEE Digital Library.

22.

Balamurugan

B.J.

, Thirusangu

and Thomas

D.G.

, Strongly multiplicative Zumkeller labeling of graphs, In: International Conference on Information and Mathematical Sciences, Elsevier (2013), 349–354.

23.

Murali

B.J.

, Thirusangu

and Madura Meenakshi

, Zumkeller cordial labeling of graphs, Advances in Intelligent Systems and Computing, Springer 412 (2015), 533–541.

24.

Murali

B.J.

, Thirusangu

and Balamurugan

B.J.

, Zumkeller cordial labeling of cycle related graphs, International Journal of Pure and Applied Mathematics 116(3) (2017), 617–627.

25.

Balamurugan

B.J.

, Thirusangu

and Thomas

D.G.

, -Zumkeller labeling for twig graphs, Electronic Notes in Discrete Mathematics, Elsevier 48 (2015), 119–126.

26.

Balamurugan

B.J.

, Thirusangu

, Thomas

D.G.

and Murali

B.J.

, -Zumkeller Labeling of Graphs, International Journal of Engineering & Technology 7(4.10) (2018), 460–463.

27.

Parsonage

, Nguyen

H.X.

, Bowden

, Knight

, Falkner

and Roughan

, Generalized Graph Products for Network Design and Analysis, 19th IEEE International Conference on Network Protocols, (2011).

28.

Tang

K.W.

and Padubirdi

S.A.

, Diagonal and toroidal mesh networks, IEEE Trans Comput 43 (1994), 815–826.

29.

Shao

, Jiang

and Vesel

, (2; 1)-Labeling of the Cartesian and strong product of two directed cycles, Mathematical Foundations of Computing 1 (2018), 49–61.

30.

Peng

and Bhaskara Rao

K.P.S.

, On Zumkeller numbers, Journal of Number Theory 133(4) (2013), 1135–1155.

31.

Sutton

, Summable graph labellings and their applications, Ph.D. dissertation, Dept. Comput. Sci., Univ. Newcastle, Newcastle upon Tyne, U.K., (2001).

32.

Dorne

and Hao

J.-K.

, Constraint handling in evolutionary search: A case study of the frequency assignment, in Parallel Problem Solving From Nature (Lecture Notes in Computer Science) 1141. Springer (1996), 801–810.

33.

Akyildiz

I.F.

, Ho

J.S.M.

and Lin

Y.-B.

, Movement-based location update and selective paging for PCS networks, IEEE/ACM Trans Netw 4(4) (1996), 629–638.

34.

Abutaleb

and Li

V.O.K.

, Location update optimization in personal communication systems, Wireless Netw 3(3) (1997), 205–216.

35.

Jung

and Tonguz

O.K.

, Random spacing channel assignment to reduce the nonlinear intermodulation distortion in cellular mobile communications, IEEE Trans Veh Technol 48(5) (1999), 1666–1675.

36.

Chartrand

, Erwin

, Harary

and Zang

, Radio labelings of graphs, Bull Inst Combinat Appl 33 (2001), 77–85.

37.

Akyildiz

I.F.

, Lin

Y.-B.

, Lai

W.-R.

and Chen

R.-J.

, A new random walk model for PCS networks, IEEE J Sel Areas Commun 18(7) (2000), 1254–1260.

38.

, Kameda

and Li

, Optimal dynamic mobility management for PCS networks, IEEE/ACM Trans Netw 8(3) (2000), 319–327.

39.

Johnson

M.A.

, Graph transforms:Aformalism for modeling chemical reaction pathways, In Graph Theory, Combinatorics, and Applications (eds. Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk). Wiley, New York (1991), 725–738.

40.

Balaban

A.T.

and Rouvray

D.H.

, Chemical applications of graph theory. In Applications of Graph Theory (eds. R. J. Wilson and L. W. Beineke). Academic Press, New York (1979), 177–221.

41.

Wiskott

, Fellous

J.M.

, Kruger

and Malsburg

C.v.d.

, Face Recognition by Elastic Bunch Graph Matching, IEEE Trans. On PAMI 19(7) (1997), 775–779.

42.

Kahraman

, Kurt

and Gökmen

, Robust Face Alignment for Illumination and Pose Invariant Face Recognition, IEEE Conference on Computer Vision and Pattern Recognition (2007), 1–7.