Using path coloring of graphs for communication in social networks

Abstract

An L (p₁, p₂, p₃, … , p_m)- labeling of a graph G, has the vertices of G assigned with non-negative integers, such that the vertices at distance j should have at least p_j as their label difference. If m = 3 and p₁ = 3, p₂ = 2, p₃ = 1, it is called an L (3, 2, 1)-labeling which is widely studied in the literature. In this paper, we define an L (3, 2, 1)-path coloring of G as a labeling g : V (G) → Z⁺ such that between every pair of vertices there exists at least one path P where in the labeling restricted to this path is an L (3, 2, 1)-labeling. Among the labels assigned to any vertex of G under g, the maximum label is called the span of g. The L (3, 2, 1)-connection number of a graph G, denoted by k_3c (G) is defined as the minimum value of span of g taken over all such labelings g. We call graphs with the special property that k_3c (G) = |V (G) | as L (3, 2, 1)-path graceful. In this paper, we obtain k_3c (G) of graphs that possess a Hamiltonian path and carry forward the discussion to certain classes of graphs which do not possess a Hamiltonian path, which is novel to this paper. Although different kinds of labeling are studied in the literature with different mathematical constraints imposed, the idea of showing the existence of a graph with a given number as its minimum labeling number has rarely been addressed. We show that given any positive integer, there always exists an L (3, 2, 1)-path graceful graph with the given integer as its k_3c (G), thus addressing the inverse question. Finally exploiting the fact that there is no gap on the k_3c (G) number line, we give an application of path colorings for secure communication on social networking sites. Efforts to deploy graph coloring in task scheduling, interference-free transmission, etc have been dealt by earlier researchers. In this paper, we deploy the L (3, 2, 1)-path coloring technique defined by us for secure communication in social networks, which has not been dealt with so far.

Keywords

Multi level distance labeling path coloring social networks

2010 Mathematics Subject Classification: 05C15, 05C40, 05C38

1 Introduction

The graphs under study in this paper are simple, connected, undirected, and finite. For standard graph theory terminology we refer [1]. The Frequency Assignment Problem (FAP) which evolved during 1980’s was the task of assigning channels (frequency) to radio stations so that interference is either avoided or minimized. The challenging aspect of the problem was to make this assignment utilizing the least possible frequency spectrum. The FAP was modeled as a graph labeling problem by Hale et al., 1980 [2] by denoting the radio stations as the vertices of a graph and edges drawn between two vertices if the corresponding stations are in close proximity and could possibly interfere. Assigning frequencies to stations was visualized as assigning non-negative integers to the vertices. The closer the stations geographically, larger had to be the difference in the labels assigned to them. More formally, an L (p₁, p₂, p₃, … , p_m)- labeling of a graph G, where m is a positive integer, assigns non-negative integers to the vertices of G such that vertices at distance j should have at least p_j as their label difference. Generally, two levels of interference have been studied in the literature by taking m = 2. In particular if p₁ = 2 and p₂ = 1, it was called the L (2, 1)-labeling problem or the distance two labeling, extensively studied in the literature [3]. The largest label used in such a labeling was called as the span of the labeling. Minimizing the span of the labeling meant minimal usage of the frequency spectrum of the FAP. The least possible value of span was called the L (2, 1)- number of the graph, denoted by λ (G). Finding λ (G), for a given graph G, is a highly non-trivial task due to the umpteen number of ways a graph can be L (2, 1)- labeled. Developing a mathematical proof to prove the minimality of λ (G) is an equally challenging task.

Inspite of this, the authors in [4], THEOREM 6.2, obtained upper bounds for λ (G) as, λ (G) ≤ Δ² + 2Δ, where Δ, is the maximum degree in the graph. Restricting themselves to graphs of diameter 2, they also improvised this bound as, λ (G) ≤ Δ². Determining λ (G) is shown to be NP-complete by relating it to the problem of finding Hamilton paths. In [5], the upper bound for the L (2, 1)- number of sun-free (SF)-chordal graphs is obtained and a polynomial time algorithm to determine λ (T) for a tree T is found. In [6], the authors have imposed the condition that the L (2, 1)-labeling be surjective and worked on cycles and circular arc graphs.

To ensure safe communication, Ruxandra Marinescu-Ghemeci in [7], seek a path between every pair of vertices such that the labeling restricted to that path satisfies L (2, 1)-labeling condition. The author called such a labeling as L (2, 1)-path coloring. The largest label used among all vertices of G, in such a labeling was called as the span of the labeling. The least value of span over all such labelings was called as the L (2, 1)- connection number of graph G, denoted by λ_c (G). We present an example to illustrate this.

In Fig. 1, as we move along the path v₁ - v₂ - v₃ - v₄, say P, we see that the adjacent vertices on the path have been assigned labels that differ by at least 2 and those at distance 2 on the path are assigned labels that differ by at least 1. So this serves an L (2, 1)- path between v₁ and v₄. Moreover, for every pair of vertices v_i, v_j in the graph, the sub path of P from v_i to v_j serves as the L (2, 1)-path between them. The highest label used here is 5, which is the span of the labeling. We now check if it is possible to further reduce the span.

Fig. 1

L (2, 1)-path coloring of G.

Consider another labeling of the same graph as shown in Fig. 2.

Fig. 2

L (2, 1)-path coloring of G with minimum span.

If we consider the same path P as earlier it fails to be an L (2, 1)-path. This is because v₂ and v₃ are adjacent but their labels do not differ by a minimum of 2. Instead if we take the path v₂ - v₁ - v₃ - v₄ say P′, then the required conditions are met. Moreover, the span is reduced to 4. As earlier, in this case also one single path, i.e., P′ serves the purpose for all pair of vertices. The natural question that arises to an inquisitive mind is that whether the further reduction of span is possible, may be by considering having different L (2, 1)- paths between different pairs of vertices. Unfortunately, the answer to the question is not in the affirmative and the following argument settles the claim.

It is impossible to reduce the span further for this graph, no matter what way we label the vertices. Since the graph has 4 vertices if the span should be reduced to a number less than 4, the label of at least two vertices should be the same. But as per the L (2, 1)-labeling, labels of two vertices may repeat if the L (2, 1)-path between them is a P_n, where n ≥ 4. But the graph in discussion has only two such paths namely P and P′, both are P₄- paths, having two internal vertices. If the end vertices of these paths receive label a, then the internal ones cannot be labeled with a, a + 1 and a - 1, again because of the L (2, 1)-labeling condition. Suppose our range set is {1, 2, 3}.

If a = 1, then both the internal vertices should receive 3.

If a = 2, then there exists no suitable label for both internal vertices.

If a = 3 both internal vertices should receive 1.

In any case we do not obtain a legitimate L (2, 1)- path coloring of G. So the least possible value of span is 4 and hence this is the L (2, 1)-connection number of the graph.

In practical situations interference can occur at levels more than two also. Hence, as an extension of L (2, 1)-labeling, Jean Clipperton et al. [8], introduced the L (3, 2, 1)-labeling by fixing m = 3 in the $L (p_{1}, p_{2}, \dot{.} ., p_{m}) -$ labeling and taking p₁ = 3, p₂ = 2, and p₃ = 1. This means that vertices at distance 1, 2, and 3 are assigned labels that differ by at least 3, 2, and 1 respectively. They defined the L (3, 2, 1)-labeling number k (G) of a graph G as the least positive integer k, where k is the highest label in any L (3, 2, 1)-labeling of G, analogous to the L (2, 1)- number λ (G). Amanathulla et al. discussed L (3, 2, 1)-labeling and L (4, 3, 2, 1)-labeling, an extension, to avoid interference at four levels for interval graphs [9].

Amalgamating the ideas of path coloring introduced by Ruxandra in [7] and the L (3, 2, 1)-labeling in [8] we conceived the idea of L (3, 2, 1)- path coloring of graphs. Here, we seek at least one path between every pair of vertices which is an L (3, 2, 1)-colored path. The formal definition with examples and remarks follow in the next section, i.e.; Section 2, where we also obtain some preliminary results. Our main results on Hamiltonian and non-Hamiltonian graphs, existence theorems and algorithm to path color a graph using the L (3, 2, 1)- condition are presented in Section 3. In Section 4, we apply this concept of path coloring to social networks with an illustration. Finally we conclude the article with some open problems in Section 5.

2 Preliminary results

Definition 2.1. A labeling g : V (G) → Z⁺ such that between every pair of vertices, there exists at least one path P, where in the labeling restricted to this path is an L (3, 2, 1)- labeling of P is called an L (3, 2, 1)-path coloring of the graph G. Among the labels assigned to any vertex of G under g, the maximum label is called the span of g. The L (3, 2, 1)-connection number of G denoted by k_3c (G) is defined as minimum value of span of g taken over all such labelings g. We call the graph L (3, 2, 1)-path graceful if k_3c (G) = |V (G) |.

Fig. 3

L (3, 2, 1)-path coloring of G.

In Fig. 3 we show an L (3, 2, 1)-path coloring of a graph G. The path v₁ - v₂ - v₃ - v₄, i.e., P serves as an L (3, 2, 1)-path, between v₁ and v₄. On this path, vertices at distance 1, 2, and 3 differ by at least 3, 2, and 1, respectively. Moreover, for every pair of vertices v_i, v_j in the graph, the sub path of P from v_i to v_j serves as the L (3, 2, 1)-path between them. The span of this labeling is 6. In fact, this is the least possible span and hence k_3c (G) =6 as explained below:

In an L (3, 2, 1)-path coloring, we are concerned about vertex labels only up to distance 3 from a given vertex. So vertices at distance more than three can have same labels. This means that any L (3, 2, 1)-path between a pair of vertices with same labels is a P_n, where n ≥ 5. The given graph has no such path and hence no labels can repeat or g is an injective function. As there are 4 vertices in the graph, k_3c (G) ≥4.

Suppose k_3c (G) =4, the range set is {1, 2, 3, 4}. In this set, the only pair of labels that differ by at least 3 are 1 and 4. So in any L (3, 2, 1)-path between v₁ and v₄, the end vertices of only one edge can be assigned with 1 and 4. As v₁ and v₄, are not adjacent, any L (3, 2, 1)-path between them will have more than one edge. Hence this possibility is ruled out and k_3c (G) >4.

Suppose k_3c (G) =5. The range set is {1, 2, 3, 4, 5}. As there are only 4 vertices in the graph and g is injective we need exactly 4 labels. So we discard one label from this set. Discarding 5 results in case, just discussed. Discarding a label other than 5, gives 4 different possible range sets namely, {2, 3, 4, 5}, {1, 3, 4, 5}, {1, 2, 4, 5}, {1, 2, 3, 5}. Further, consecutive labels can be assigned to vertices at a distance 3 or more only. Choosing P, i.e., v₁ - v₂ - v₃ - v₄ as the L (3, 2, 1)- path between v₁ and v₄, one pair of consecutive integers may be assigned to v₁ and v₄. If we decide to make v₁ - v₃ - v₄ as L (3, 2, 1)-path between v₁ and v₄, even a single pair of consecutive integers cannot be accommodated as labels. The same happens if P′, i. e., v₂ - v₁ - v₃ - v₄ is chosen as the L (3, 2, 1)- path between v₂ and v₄. But each of the range sets listed above has more than one pair of consecutive integers and any assignment would not yield an L (3, 2, 1)-path coloring of G. Hence k_3c (G) ≥6. In fact the labeling shown in Fig. 3 proves 6 is sufficient. Therefore, k_3c (G) =6. Even for a simple graph, as the one considered above, we can observe that it is a highly non-trivial task to find the L (3, 2, 1)-connection number. As the number of vertices, edges, and paths between vertices increases it becomes all the more tedious to compute this number.

Remark 2.2. Let g : V (G) → Z⁺ be an L (3, 2, 1)-path coloring of a graph G with span (g) = k_3c (G), then g is called an optimal L (3, 2, 1)-path coloring of G.

Remark 2.3. As there exists exactly one path between every pair of vertices in a tree, the definition of L (3, 2, 1)-labeling and L (3, 2, 1)-path coloring coincide and hence k_3c (T) = k (T), for any tree T.

We recall the following two results for ready reference from Jean Clipperton et al., [8] on k (P_n) and k (K_1,n). P_n, is the path on n vertices and K_1,n is the star graph in which one central vertex is adjacent to n pendant vertices. By Remark 2.3 these are also the results for k_3c (P_n) and k_3c (K_1,n) respectively. Throughout the rest of this article we use these results for k_3c (P_n) and k_3c (K_1,n) respectively.

Theorem 2.4. ([8], Theorem 5) For any path P_n, n ≥ 2, $k (P_{n}) = {\begin{matrix} 1, & if n = 1 \\ 4, & if n = 2 \\ 6, & if 3 \leq n \leq 4 \\ 7, & if 5 \leq n \leq 7 \\ 8, & if n \geq 8 \end{matrix}$

The authors here have obtained the above result by repeating the pattern 3, 6, 1, 4, 7, 2, 5, 8 along the vertices of the path when n ≥ 8.

Theorem 2.5. ([8], Corollary 3) For star graph with n ≥ 1, k (K_1,n) =2n + 2

Here the authors have obtained the result by assigning label 1 to central vertex of the star and 4, 6, 8, …2n + 2 to the pendant vertices.

We now present some preliminary results on k_3c (G) for any graph G, in this section and our main results in the next section.

Proposition 2.6. For a connected graph G with n ≥ 2 vertices,

k_3c (G) ≥ k_3c (P_r) ≥ k_3c (P_diam(G)+1) ≥4, where r ≥ diam (G) +1.

Proof. The last inequality is obvious as any connected graph with at least 2 vertices has diameter at least 1. By Theorem 2.4 and Remark 2.3 the result holds.

Let g be an optimal L (3, 2, 1)-path coloring of G. Let y and z be two vertices which are at a distance equal to diam (G). Then any L (3, 2, 1)-path P_r between y and z has a minimum of diam (G) +1 vertices and contains a sub path isomorphic to P_diam(G)+1. Hence by Theorem 2.4 and Remark 2.3 we have the second inequality.

As P_r is a sub graph of G, the span of any L (3, 2, 1)- path coloring of the graph G is at least as much as k_3c (P_r). k_3c (G) is the minimum value of span, the first inequality holds.□

k_3c (G) ≤ k_3c (H) +3 (n - p), where H is any induced subgraph of G with p ≤ n vertices.

Proof. The equality holds if n = p because H = G. The inequality follows by the definition of L (3, 2, 1) -path coloring. An optimal labeling of H can be extended to G as follows: An increase of 3 starting from the value of k_3c (H) is progressively assigned to the vertices of G that are not in H, in any order, then we get an L (3, 2, 1) -path coloring of G with span k_3c (H) +3 (n - p). k_3c (G) being the least value of span the result holds.□

If the graph G has n bridges incident on the same vertex then k_3c (G) ≥2n + 2

Proof. If uu₁ and uu₂ are adjacent bridges then the only path between u₁ and u₂ is u₁ - u - u₂. Hence n bridges incident in the same vertex induce a subgraph H in G, isomorphic to K_1,n such that any L (3, 2, 1)-path coloring of G induces a L (3, 2, 1)-path coloring of H. Thus we have k_3c (G) ≥ k_3c (K_1,n) = k (K_1,n) =2n + 2. By Remark 2.3 and Theorem 2.5 the result holds.□

k_3c (G) ≤ k_3c (H) where H is a spanning connected subgraph of the graph G.

Proof. H is a spanning connected subgraph of G containing all the vertices of G. So, any L (3, 2, 1)-path coloring of H is also L (3, 2, 1)-path coloring of G. The edges in G that are not in H, create new paths in G and this may result in a smaller span and hence k_3c (G) ≤ k_3c (H).□

k_3c (G) = k_3c (H) = k (H), if H is a Hamiltonian path in G.

Proof. H is a spanning connected subgraph of G. Hence by the point(4) of the same proposition we have, k_3c (G) ≤ k_3c (H).

Let d_P (u, v) and d_H (u, v) denote the distance between the vertices u and v along any path P and along the Hamiltonian path H respectively. Then d_P (u, v) ≤ d_H (u, v). Let g be an optimal L (3, 2, 1)- path coloring of G considering P as the L (3, 2, 1)- path between u and v with span k_{3c_P} (G). Then |g (u) - g (v) |≥4 - d_P (u, v) ≥4 - d_H (u, v). So g is also an L (3, 2, 1)- path coloring of G, taking H as the L (3, 2, 1)- path between u and v. So k_3c (P_n) = k_{3c_H} (G) ≤ k_{3c_P} (G) where k_{3c_H} (G) is the least span obtained considering H as the L (3, 2, 1)- path between u and v. Hence the result holds. □

If G contains a Hamiltonian path, the value of k_3c (G) does not exceed 8, whatever be the number of vertices in the graph. Repeating the pattern 3, 6, 1, 4, 7, 2, 5, 8 along the Hamiltonian path, we get an L (3, 2, 1)-path coloring of G with minimum span. The natural question that arises is about the k_3c (G) of more general graphs, i.e., the ones that do not contain a Hamiltonian path. Are there any such graphs which have the k_3c (G) value as less as 8 ? Our next Theorem 3.1 on complete bipartite graphs explores the same and answers this question in the affirmative. Surprisingly, though not all complete bipartite graphs posses a Hamiltonian path, this class of graphs, have their k_3c (G) stabilizing at 8. The results on complete bipartite graphs and bistars are presented in the next section. The results on the star graph, which is a special case of complete bipartite graph and that of the bistar lead us to state and prove the existence theorem, which is presented later in the next section. That is given any positive integer a, we prove that there always exists a graph G, such that k_3c (G) = a. Lastly, we present an algorithm to L (3, 2, 1)-path color a graph whose k_3c (G) = a. The algorithm takes the value of a as input and produces the L (3, 2, 1)-path coloring of the graph whose k_3c (G) = a.

3 Path coloring of some standard graphs, existence theorems and algorithm to path color a graph

The complete bipartite graph K_m,n is a special kind of graph whose vertex set is partitioned into two sets V₁ and V₂ with m and n vertices respectively. Every vertex of V₁ is adjacent to every vertex of V₂ and no two vertices of the same set are adjacent. If m = 1 then it is the star graph.

Theorem 3.1. Let 1 ≤ m ≤ n. Then $k_{3 c} (K_{m, n}) = {\begin{matrix} 2 n + 2, & if m = 1, n \geq 1 \\ 6, & if n = m = 2 \\ 7, & if (m = 2, n = 3) or \\ (m = 3, n = 3) or \\ (m = 3, n = 4) or \\ 8, & otherwise \end{matrix}$

Proof. Case 1: When m = 1, n ≥ 1 the proof holds by Remark 2.3 and Theorem 2.5.

Case 2: For n = m = 2, the graph is a cycle on 4 vertices and the result holds by point(5) of Proposition 2.6.

Case 3: In all these 3 cases, G has 5 ≤ m + n ≤ 7 vertices and possess a Hamiltonian path. Then by point(5) of Proposition 2.6, k_3c (K_m,n) =7.

Case 4: This is the case where the number of vertices of the graph exceeds 7 or does not contain a Hamiltonian path. So k_3c (G) ≥8. We exhibit a labeling below to prove that 8 is sufficient.

Let V (K_m,n) = {y₁, y₂, … , y_m} ⋃ {z₁, z₂, … , z_n} where 2 ≤ m ≤ n with m + n ≥ 6.

Define the labeling g as follows: $g (x) = {\begin{matrix} 1, & if x = y_{1} \\ 6, & if x = z_{1} \\ 3, & if x = y_{j}, 2 \leq j \leq m \\ 8, & if x = z_{k}, 2 \leq k \leq n \end{matrix}$

The example of K_3,5 is shown in Fig. 4. As k_3c (K_3,5) =8 = |V (K_3,5) | it is L (3, 2, 1)-path graceful. It can be easily seen that between each pair of vertices of K_m,n there is an L (3, 2, 1)-path coloring as follows:

For every j, 2 ≤ j ≤ m, the path from y₁ to y_j is [y₁, z₁, y_j].

For every j, 2 ≤ jtextlessk ≤ m, the path from y_j to y_k is [y_j, z₂, y₁, z₁, y_k].

For every j, 2 ≤ j ≤ n, the path from z₁ to z_j is [z₁, y₁, z_j].

For every j, 2 ≤ jtextlessk ≤ n, the paths from z_j to z_k is [z_j, y₁, z₁, y₂, z_k].

For every j, k, 1 ≤ j ≤ m, 1 ≤ k ≤ n, the path from y_j to z_k is [y_j, z_k].□

Fig. 4

L (3, 2, 1)-path coloring of K_3,5.

As a consequence of the Theorem 3.1, we have the following Corollary 3.2:

Corollary 3.2. From the above Theorem 3.1, given any even positive integer a ≥ 4, there exists a star graph $K_{1, \frac{(a - 2)}{2}}$ such that $k_{3 c} (K_{1, \frac{(a - 2)}{2}}) = a$ .

The bistar B_n,n, is the graph obtained my making the central vertices of two copies of the star graph K_1,n adjacent.

Theorem 3.3. k_3c (B_n,n) =2n + 5 where B_n,n ; n ≥ 2 is the bistar graph.

Proof. Let the vertex set be V (G) = {u, u₁, u₂, . . . u_n, u_n+1, v₁, v₂, . . . v_n} where u and u₁ are the center vertices of two stars K_1,n. The bistar has n + 1 bridges incident on a single vertex u. Hence, k_3c (B_n,n) ≥2n + 4. By Proposition 2.6 point 3. Suppose k_3c (B_n,n) =2n + 4. From [8], we see that an optimal L (3, 2, 1)- labeling of K_1,n+1 assigns 1 to the central vertex and 4, 6, 8 … (2n + 4) to the pendant vertices. The remaining n vertices of the bistar need to be labelled. But the bistar does not contain a P_n where n ≥ 5 and hence none of the labels used earlier for K_1,n+1 can be reused. Moreover, the labels 2, 3, and 5 cannot be used by the definition L (3, 2, 1)- path coloring. This leaves us with n - 1 labels 7, 9 . …2n + 3 for the remaining n vertices of the bistar, which is insufficient. Therefore, k_3c (B_n,n) ≥2n + 5.

We now exhibit an L (3, 2, 1) -path coloring of the bistar with span 2n + 5, which proves the required result. Define the labeling g as follows: $g (x) = {\begin{matrix} 1, & if x = u \\ 2 i + 2, & if x = u_{i}, 1 \leq i \leq n + 1 \\ 2 i + 5, & if x = v_{i}, 1 \leq i \leq n \end{matrix}$

It can be easily seen that between each pair of vertices of B_n,n there is an L (3, 2, 1)-path coloring as follows:

For every i, 1 ≤ i ≤ n + 1, the path from u_i to u is [u_i, u].

For every i, j, 2 ≤ i ≤ j ≤ n, the path from u_i to v_j is [u_i, u, u₁, v_j].

The path from u_i to u_j is [u_i, u, u_j] for all i, j, 1 ≤ itextlessj ≤ n + 1.

For every i, 1 ≤ i ≤ n, the path from v_i to u₁ is [v_i, u₁].

The path from v_i to u is [v_i, u₁, u] for all i, 1 ≤ i ≤ n.

The path from v_i to v_j is [v_i, u₁, v_j] for all i, j, 1 ≤ itextlessj ≤ n.□

The particular case of B_4,4 is shown in the Fig. 5.

Fig. 5

L (3, 2, 1)-path coloring of B_4,4.

As a consequence of the above Theorem 3.3, we have the following Corollary 3.4:

Corollary 3.4. Given any odd positive integer a ≥ 9, there exists a bistar $B_{\frac{(a - 5)}{2}, \frac{(a - 5)}{2}}$ such that $k_{3 c} (B_{\frac{(a - 5)}{2}, \frac{(a - 5)}{2}}) = a$ .

It is clear that, given any positive integer except 2, 3 and 5, we always have a graph for which the given number is the k_3c (G). For 1 and 7, we have paths P₁ and P₇ such that k_3c (P₁) =1 = |V (P₁) | and k_3c (P₇) =7 = |V (P₇) |. So P₁ and P₇ are L (3, 2, 1)-path graceful. For any integer a ≥ 4 and a ≠ 5, 7 we have stars and bistars whose k_3c (G) is the given integer. This proves that there is no gap in the k_3c (G) number line except at 2, 3, and 5 but these graphs are not L (3, 2, 1)-path graceful. Our next two Theorems 3.5 and 3.6 shows that star and bistars are not the only graphs that can be constructed for a given value of k_3c (G) but more complex ones exist and they have the star and bistar as induced subgraphs. Moreover, these graphs have the special property of being L (3, 2, 1)-path graceful. In the next two Theorems 3.5 and 3.6, we prove that for every positive integer a ≥ 8, there always exists a graph of order a which is L (3, 2, 1)-path graceful.

Theorem 3.5. For any even integer a ≥ 8, there always exists a graph G with k_3c (G) = |V (G) | = a.

Proof. Let $K_{1, \frac{(a - 2)}{2}}$ be the star graph centered at the vertex u and having pendant vertices $u_{1}, u_{2}, . . . u_{\frac{(a - 2)}{2}}$ . Let $K_{3, \frac{(a - 4)}{2}}$ be the complete bipartite graph with vertex sets {v, v₁, v₂} and ${v_{3}, v_{4}, v_{5}, \dots v_{\frac{a}{2}}}$ . Now consider the graph G obtained by identifying the vertex u₁ of the star graph with vertex v of the complete bipartite graph.This graph has $\frac{(a - 2)}{2}$ bridges incident on the vertex u. Hence, k_3c (G) ≥ a, by Proposition 2.6 point (3).

We exhibit a labeling g below with span a and prove that it is L (3, 2, 1)-path coloring. $Let g (x) = {\begin{matrix} 7, & if x = v_{3} \\ 2, & if x = v_{1} \\ 5, & if x = v_{4} \\ 8, & if x = v_{2} \\ 1, & if x = u, v_{i}, 5 \leq i \leq \frac{a}{2} \\ 2 i + 2, & if x = u_{i}, 1 \leq i \leq \frac{(a - 2)}{2} \end{matrix}$

It can be easily seen that between each pair of vertices of G there is an L (3, 2, 1)-path coloring as follows:

For every i, $1 \leq i \leq \frac{a - 2}{2}$ , the path from u to u_i is [u, u_i].

The path from u to v₁ is [u, u₁, v₃, v₁].

The path from u to v₂ is [u, u₁, v₃, v₁, v₄, v₂].

The path from u to v₃ is [u, u₁, v₃].

The path from u to v₄ is [u, u₁, v₃, v₁, v₄].

For every i, $5 \leq i \leq \frac{a}{2}$ , the path from u to v_i is [u, u₁, v₃, v₁, v₄, v₂, v_i].

For every i, j, $1 \leq i j \leq \frac{a - 2}{2}$ , the path from u_i to u_j is [u_i, u, u_j].

The path from u₁ to v₁ is [u₁, v₃, v₁].

The path from u₁ to v₂ is [u₁, v₃, v₁, v₄, v₂].

The path from u₁ to v₃ is [u₁, v₃].

The path from u₁ to v₄ is [u₁, v₃, v₁, v₄].

For every i, $5 \leq i \leq \frac{a}{2}$ , the path from u₁ to v_i is [u₁, v_i].

For every i, $2 \leq i \leq \frac{a - 2}{2}$ , the path from u_i to v₁ is [u_i, u, u₁, v₃, v₁].

For every i, $2 \leq i \leq \frac{a - 2}{2}$ , the path from u_i to v₂ is [u_i, u, u₁, v₃, v₁, v₄, v₂].

For every i, $2 \leq i \leq \frac{a - 2}{2}$ , the path from u_i to u₁ is [u_i, u, u₁].

For every i, $2 \leq i \leq \frac{a - 2}{2}$ , the path from u_i to v₄ is [u_i, u, u₁, v₃, v₁, v₄].

For every i, j, $2 \leq i \leq \frac{a - 2}{2}$ , $5 \leq j \leq \frac{a}{2}$ , i ≤ j, the path from u_i to v_j is [u_i, u, u₁, v₃, v₁, v₄, v₂, v_j].

For every i, j, $5 \leq i j \leq \frac{a}{2}$ , the path from v_i to v_j is [v_i, u₁, v₃, v₁, v₄, v₂, v_j].□

Fig. 6

L (3, 2, 1)-path coloring of G with a = 10.

Theorem 3.6. For any odd integer a ≥ 9, there always exists a graph G with k_3c (G) = |V (G) | = a.

Proof. Consider the bistar with two centers u and v. Let u_i and v_i where $1 \leq i \leq \frac{a - 5}{2}$ be the pendant vertices adjacent to u and v, respectively. Consider two paths P₃ : x₀ - x₁ - x₂ and P₂ : y₀ - y₁. Let G be the graph obtained by identifying x₀ with u₁ and y₀ with v₁. G has $\frac{a - 3}{2}$ bridges incident on the single vertex u. Hence k_3c (G) ≥ a - 1. (By Proposition 2.6 point (3). Any optimal L (3, 2, 1)- path coloring of a bistar assigns 1 and 4 to the two central vertices, 6, 8, 10 . . . a - 1 to the pendant vertices adjacent to the central vertex labelled with 1 and 7, 9, . . ., a to the pendant vertices adjacent with the central vertex labeled 4 as in Theorem 3.3. So, k_3c (G) ≥ a.

We now exhibit a labeling on V (G) with span a, which proves the required result.

Let $g (x) = {\begin{matrix} 1, & if x = u \\ 4, & if x = v \\ 3, & if x = x_{1} \\ 8, & if x = x_{2} \\ 2, & if x = y_{1} \\ 2 i + 4, & if x = u_{i}, 1 \leq i \leq \frac{a - 5}{2} \\ 2 i + 5, & if x = v_{i}, 1 \leq i \leq \frac{a - 5}{2} \end{matrix}$

Fig. 7

L (3, 2, 1)-path coloring of G with a = 11.

It can be easily seen that between each pair of vertices of G there is an L (3, 2, 1)-path coloring as follows:

The path of length 6, i. e., x₂ - x₁ - u₁ - u - v - v₁ - y₁ forms an L (3, 2, 1)-path. It’s enough to show that there is an L (3, 2, 1)-path from u_i and v_i to all the other vertices of G.

For every i, $2 \leq i \leq \frac{a - 5}{2}$ , the path from u_i to u₁ is [u_i, u, u₁].

For every i, $2 \leq i \leq \frac{a - 5}{2}$ , the path from u_i to x₁ or x₂ is [u_i, u, u₁, x₁] or [u_i, u, u₁, x₁, x₂] respectively.

The path from u_i to v₁ is [u_i, u, v, v₁] for all i, $2 \leq i \leq \frac{a - 5}{2}$ .

For every i, j, $2 \leq i \leq j \leq \frac{a - 5}{2}$ , the path from u_i to v_j is [u_i, u, v, v_j].

The path from u_i to y₁ is [u_i, u, v, v₁, y₁] for all i, $2 \leq i \leq \frac{a - 5}{2}$ .

The path from v_i to y₁ is [v_i, v, v₁, y₁] for all i, $2 \leq i \leq \frac{a - 5}{2}$ .

For every i, $2 \leq i \leq \frac{a - 5}{2}$ , the path from v_i to x₁ or x₂ is [v_i, v, u, u₁, x₁] or [v_i, v, u, u₁, x₁, x₂] respectively.

The path from v_i to u₁ is [v_i, v, u, u₁] for all i, $2 \leq i \leq \frac{a - 5}{2}$ .□

We now present an algorithm to obtain an L (3, 2, 1)-path coloring of a graph G whose k_3c (G) = a. The graphs can be first constructed as explained in Theorems 3.5 or 3.6 as the case may be and then the labeling can be done using this algorithm.

Algorithm 1 To obtain an L (3, 2, 1)-path coloring of a graph whose k_3c (G) = α
1: procedureL (3, 2, 1) - pathcoloring(a)
2: ifa ≡ 0 mod 2 then
3: g (v₃) ←7
4: g (v₁) ←2
5: g (v₄) ←5
6: g (v₂) ←8
7: g (u) ←1
8: fori = 1 to $\frac{(a - 2)}{2}$ do
9: g (u_i) ←2i + 2
10: end for
11: fori = 5 to $\frac{a}{2}$ do
12: g (v_i) ←1
13: end for
14: else
15: g (u) ←1
16: g (v) ←4
17: g (x₁) ←3
18: g (x₂) ←8
19: g (y₁) ←2
20: fori ← 1 to $\frac{(a - 5)}{2}$ do
21: g (u_i) ←2i + 4
22: g (v_i) ←2i + 5
23: end for
24: end if

If a is even the complexity of the algorithm is obtained as follows:

Statements 3 to 7 being assignment statements are of order 1 each. The statement 9 that involves three operations namely one addition, one multiplication and one assignment statement is executed $\frac{(a - 2)}{2}$ times. Statement 12 is an assignment statement executed $\frac{(a - 8)}{2}$ times. Hence, $5 + 3 * \frac{(a - 2)}{2} + \frac{(a - 8)}{2} = O (a)$ .

If a is odd then the complexity of the algorithm is as follows:

Statements 15 to 19 being assignment statements are of order 1. Statements 21 and 22 involve 3 operations each as explained in the previous case and are executed $\frac{(a - 5)}{2}$ times. So the total number of operations involved are $5 + 6 * \frac{(a - 5)}{2} = O (a)$ .

In both cases the algorithm is a polynomial in the input a. Since the graph can be constructed for any given integer a and labeled in polynomial time we next present an application of this in social networks for secure communication.

4 Applying path coloring for secure communication in social networks

Security issues need to be given prime importance on social networking sites and users are often unaware about how their privacy is compromised [10, 11]. Enhanced security is required when image posts are shared compared to text [12]. Different kind of labeling techniques like the radio mean labeling have been used in securing messages [13]. Encrypted text is sent to receiver as a sequence of edges or vertices of cipher graph. Using the cipher graph, receiver can decrypt the received sequence of numbers to original text message. In [14], the same authors have applied L (3, 2, 1)-path coloring to star graphs K_1,n for encryption and decryption. Here we apply the above theory of L (3, 2, 1)-path coloring for secure communication. Suppose there is a group of people who need to communicate with each other securely. Anyone in the group can send a message to any other but the message has to pass through a specific set of people before it reaches the receiver(may be to follow a hierarchy). For example in the Fig. 4 suppose y₁ represents the principal of an institution and the remaining y_i’s are faculty working under him. z₁ is the director of the institution and z_i’s are heads of various sections like controller of exams, head of student affairs, hostel warden and so on. If the principal wants to send a communication to the faculty he needs to take prior approval from the director and then do so. So the L (3, 2, 1)-path y₁ - z₁ - y_j can be used. Similarly the path y_j - z₂ - y₁ - z₁ - y_k could be used if y_j wants to communicate with y_k, a matter related to the portfolio of z₂. But this communication has to pass through the concerned head, the principal, and he in turn takes consent of the director and finally the message reaches y_k and so on. Unique paths involving a different set of people exists and the most suitable one could be chosen. This would avoid unwanted messages to people who are not concerned with the issue thus saving their time and respecting their privacy. Edge labels could be found as difference in the labels of end vertices and that could be treated as time or cost involved in the communication. Since we are seeking a path coloring with minimum span it could mean a faster or cheaper communication.

Exploiting the idea of existence of a graph for any given integer a ≥ 8, whose k_3c (G) = a we propose a method for safe communication. This can be done along a L (3, 2, 1)-path between the sender and the receiver, the vertices along the path represent those set of people through whom the message has to pass through. If there is more than one such path then the sender and the receiver can decide on which path to communicate before the communication begins. The original message is sent by the sender in an encrypted form, using an encryption rule and the next person who receives this message has to decrypt this. He passes on the message to another person applying a different encryption rule and the process continues till it finally reaches the intended recipient. So each time the message goes through a new person, it gets more and more secure.

The following information is made known to the members of the group before the communication begins:

An integer a, is made known to all members of the group before communication starts. Based on whether a is even or odd, all the members construct the graph as explained in Theorems 3.5 and 3.6 and label the vertices using the Algorithm 1 in polynomial time. The edge e_ij incident between two adjacent vertices v_i and v_j along an L (3, 2, 1)-path is labeled as g (v_i) - g (v_j).

Keyword to be used.

THE PROCESS

At first the blank spaces if any in the plain text are removed. Then the plain text is divided into digrams or pairs of letters. If the message consists of an odd number of letters, a rare letter like x is appended at the end of the text. If a letter is repeated in both positions of the digram, break the pair and pair one letter with x and other with the next letter in the plain text.

The 6*6 Playfair matrix is constructed with the keyword written in the first row, which is then filled by the remaining characters of English alphabet a - z and numbers 0-9 in order. Then apply the following rules on the digrams obtained in step 1.

If both letters of the digram are in the same column then each letter of the digram is replaced by a letter immediately below it. If a letter in the digraph is in the last row, then it is replaced with the letter on first row of the same column.

If both letters of the digram are in the same row then each letter of the digram is replaced by a letter immediately to its right. If a letter in the digraph is in the last column, then it is replaced with the letter on first column of the same row.

If both letters of the digram belong to different row and column of the Playfair matrix, then consider the submatrix having these two letters on one pair of its diagonally opposite corners. The first letter in the digram is then replaced by the letter which lies in the row of the first letter and column of the second. The second letter in the digram is replaced by the letter which lies in the column of the first letter and row of the second.

Let C be the text obtained after the Playfair encryption. Next the 26 english alphabets and the 10 numerals are represented as the vertices of the cycle C₃₆ in the clockwise direction and then a circular permutation of C is obtained as follows: Suppose the text message is to be sent from v_i to v_j, along a L (3, 2, 1)-path between them. If v_l is adjacent to v_i on the path, then v_i moves C on C₃₆ in the clockwise direction by a number of steps equal to the label of e_il if it is positive and in the anticlockwise direction if negative and obtains the corresponding alphanumeric sequence N and sends it to v_l.

If v_l wants to decrypt the message N, on the same C₃₆ he moves N in the anti clockwise direction by a number of steps equal to the label of e_il if it is positive and in the clockwise direction if negative and the corresponding playfair text C is obtained. Applying the reverse play fair rules he gets the plain text P sent by the sender v_i.

Next v_l has to send the message to say v_k on the L (3, 2, 1) path. He considers the alpha numeric sequence N sent by v_i. Moves it on C₃₆ in the clock wise direction by a number of steps equal to e_lk if it is positive and in the anticlockwise direction if negative and obtains a new alpha numeric sequence M. If v_k wants to decrypt this he finds the sum of edge weights e_il and e_lk. If this sum is positive he moves M in the anticlockwise direction on C₃₆ by a number of steps equal to the sum and if negative in the clockwise direction. This leads him to the cipher text C. Applying reverse playfair rules he gets to the original plain text P.

This process continues till the message reaches the final recipient v_j.

ILLUSTRATION:

The following information is made known to all members of the group

a = 11

Keyword =“strict”.

The corresponding playfair matrix would be:

s	t	r	i	c	a
b	d	e	f	g	h
j	k	l	m	n	o
p	q	u	v	w	x
y	z	0	1	2	3
4	5	6	7	8	9

The members construct the graph as shown in Fig. 7 and label the vertices and edges using the Algorithm 1. Suppose the plain text is “examination” to be sent from x₂ to u.

The plain text P is divided into pairs of letters: ex, am, in, at, io, nx. Since the length is odd, x is appended at the end.

Applying Playfair rules mentioned in step 2 of encryption process we get the cipher text, C as:

huiocmsramow.

The edge from x₂ to x₁ has weight 5. Each alphabet in C is moved on C₃₆ by 5 steps in the clockwise direction. Thus x₂ obtains the alpha numeric sequence N as mznthrxwfrt1. Now x₁ may decrypt this by moving on C₃₆ 5 steps in the anticlockwise direction. He gets the cipher text C, to which he applies the reverse play fair rules and obtains the plain text P.

x₁ is adjacent to u₁ and the weight of the edge between them is -3. If he wishes to pass the message to u₁, he moves N on C₃₆ in anticlockwise direction by 3 steps and he obtains the new alphanumeric sequence M as jwkqeoutcoqy.

If u₁ has to decrypt this he sums up the weights of the first two edges on the L (3, 2, 1)- path. This sum is 5 - 3 =2, which is positive. So on C₃₆ he moves the message M by 2 steps in the anticlockwise direction to get the cipher text C. On using the reverse play fair rules the original plain text can be obtained.

Next the message moves from u₁ to u. The weight of the edge connecting them is 5. So u₁ moves the message M by 5 units in the clockwise direction to get the new message say K as o1pvjtzyhtv3. Next u sums up the edge weight of the three edges on the L (3, 2, 1)-path and gets 5 - 3 +5 = 7. He now moves K on C₃₆ in anticlockwise direction by 7 steps to get the cipher text C. Applying reverse playfair rules to C the plain text P is obtained. As the value of a, the method of constructing the graph and labeling using the L (3, 2, 1) path coloring with minimum span is known only to the members in the group, the communication remains secure. Moreover when there are multiple L (3, 2, 1) paths it becomes difficult for any intruder to hack information.

If the number of people in the group, i.e., a is fixed then the graph and its labeling remains fixed. To bring a variation in this one of the members in the group can be made ’Dummy’. This is made known to the members just before the communication starts. Suppose in the above example x₁ is made dummy, then an edge of weight 8 - 6 =2 can be assumed from x₂ to u₁. Accordingly all the edge weights change hence the number of moves on C₃₆ changes. Since the ’Dummy’ tag is attached to a vertex just before communication starts, the graph changes dynamically and so do the L (3, 2, 1)- paths which make hacking difficult for an intruder.

5 Conclusion and scope for future work

The idea of path coloring discussed in the paper may be extended to higher levels by taking m = 3, 4, …. The authors are working towards generalizing this idea upto m = diam (G) levels. A more generalised version of the above path coloring would be to seek k internally disjoint L (3, 2, 1) paths between all pairs of vertices and obtain the k - L (3, 2, 1) connection number of G. These k paths can add more complexity for an intruder and application of these ideas for secure communication in social networking may be explored.

References

West

D.B.

Introduction to Graph theory (Vol. 2), Upper Saddle River: Prentice Hall, 2001.

Hale

W.K.

, Frequency assignment: theory and applications, Proceedings of the IEEE 68(12) (1980), 1497–1514.

Georges

and Mauro

, Generalized vertex labeling with acondition at distance two, Congr. Number 109 (1995), 141–159.

Griggs

J.R.

and Yeh

R.K.

, Labeling graphs with a condition atdistance 2, SIAM J. Discrete Math. 5 (1992), 586–595.

Chang

G.J.

and Kuo

, The L (2, 1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996), 309–316.

Amanathulla

S.K.

and Pal

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

Marinescu-Ghemeci

, On radio connection number of graphs, Discussiones Mathematicae Graph Theory 39(3) (2019), 705–730.

Clipperton

, Gehrtz

, Szaniszlo

, Torkornoo

L(3, 2, 1)-Labeling of simple graphs, VERUM, Valparaiso University, 2006.

Amanathulla

S.K.

and Pal

, L (3, 2, 1)- and L (4, 3, 2, 1)-labelingproblems on interval graphs, AKCE International Journal ofGraphs and Combinatorics 14 (2017), 205–215.

10.

Neethu

M.R.

and Harini

, A Model to Ensure Business Ethics inSocial Networks, International Journal of Scientific andTechnology Research 8(10) (2019), 586–591.

11.

Pushpa

B.R.

A new technique for data encryption using DNA sequence, Proceedings of 2017 International Conference on Intelligent Computing and Control(I2C2), (2018), 1–4.

12.

Neethu

M.R.

and Harini

, Securing image Posts in SocialNetworking Sites, Lecture Notes in Computational Vision andBiomechanics, Springer Netherlands 28 (2018), 79–91.

13.

Meera Saraswathi , Meera

K.N.

AnApplication of Radio Mean Labeling in Cryptography, IEEE 3rd PhD Colloquium on Ethically Driven Innovation and Technology for Society (PhD EDITS) IEEE (2021), 1–2.

14.

Dhanyashree , Meera

K.N.

An Illustration of L(3, 2, 1)- path Coloring in Cryptography, IEEE 3rd PhD Colloquium on Ethically Driven Innovation and Technology for Society (PhD EDITS) IEEE (2021), 1–2.