Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 212 https://internationalpubls.com Locally Harmonious Chromatic Number of Certain Tree-Structured Networks M. Siva1, K. Lenin Muthu Kumaran1, A Nelson2, K. Suresh3,*, S. Arul Amirtha Raja3 1Department of Mathematics, Shanmuga Industries Arts and Science College, Tiruvannamalai 606603 2Department of Mathematics, Panimalar Engineering College, Chennai 600123. 3Department of Mathematics, St. Joseph's College of Engineering, OMR, Chennai 600119 ∗Corresponding author: dhivasuresh@gmail.com Article History: Received: 24-09-2024 Revised: 04-11-2024 Accepted: 19-11-2024 Abstract: Graph coloring is one of the oldest and best-known problems of graph theory. The locally harmonious coloring of G is a proper vertex coloring in which adjacent edges receive different color pairs [3]. In another way, all the vertices in N [v] receive different colors for all v in G. The minimum number of colors required to obtain a locally harmonious coloring of a graph G is called the locally harmonious chromatic number of G and is denoted by h1(G). In this paper, we investigate the locally harmonious chromatic number of slim tree, hypertree, shuffle hypertree and l-complete binary tree. Keywords: coloring; locally harmonious coloring; slim tree; hypertree; shuffle hypertree; l- complete binary tree. 1. Introduction The introduction of a method for very high scale integration, which will allow the manufacture of a single silicon chip with one million active devices in five years, has also changed the limits on a multiprocessor interconnection network. With advancements in technology, active devices are becoming smaller, faster, and consuming less power. The speed gap between signals that are wholly internal to the device and those that must transit through package pins, on the other hand, is expanding. Consequently, a good VLSI building block could be a single integrated circuit standalone device [10]. Later, a wide range of networks, including lattices or trees, are considered because these structures seem to be appealing because the future computer systems are easily expandable. It’s not shocking, then, that tree-structured networks have recently sparked a lot of interest. Trees are a specific type of graph that are worth studying if only because they are used in so many different domains of practise and science. These graphs that do not have any cycles. They are naturally expandable, and even unbalanced trees retain the majority of the features that make them interesting. As a result, the package periphery is still another physical hindrance, and connectivity topologies with few ports per node should be considered. A binary tree structure with only three ports per node appears to be particularly suitable if the number of ports per node must be limited to a minimum. Additional links, on the other hand, are required to provide redundant paths, which are Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 213 https://internationalpubls.com the foundation for a fault-tolerant message routing system. These linkages can also be used to reduce the average distance between nodes and ensure that message density is consistent across all routes. Because of their simple routing algorithms, the binary trees which contain half-ring and full ring emerged as potential competitors after an intense search for the ideal placement of these additional linkages. Trees are essential for understanding the structure of graphs and have a far-reaching range of ap- plications, which includes data processing. Additional properties such as roots and vertex- orderings are common in tree architectures. Trees play a crucial role in the structuring and scrutinizing of connected networks, as well as in the structural comprehension of graphs and the algorithms of information processing. Trees, in fact, form the foundation of optimally connected networks. One of the most important tasks in information management is determining how to store data in a space- efficient manner that simultaneously allows for quick retrieval and change. Tree-based systems are frequently the most effective means of reconciling these competing objectives. The locally harmonious coloring [3] of a graph G is a proper vertex coloring in which every color- pair is present only once for every edge within distance one from any vertex v in V (G). It leads to the constraint that all vertices in the closed neighborhood N [v] receive different colors for every vertex v in G. The minimum number of colors required to obtain a locally harmonious coloring of a graph G is called the locally harmonious chromatic number of G and is denoted by h1(G). Given a graph G, the locally harmonious coloring problem is to determine h1(G). In 2015, W. Gao [3] proposed three algorithms to estimate h1(G). These algorithms have high impact on time complexity due to an exhaustive search on vertices and branching rules. The concept of locally harmonious coloring is derived from d harmonious coloring [11], as a proper vertex coloring such that every color pair is present at most once for every edge within distance d; during the conference held in Taiwan. The locally harmonious coloring is exactly same as d harmonious coloring when d=1. 2. lh-Coloring of Certain Tree-Derived Networks In this section, we present the lh-Coloring Lemma in which we obtain the lower bound of locally harmonious coloring for Hypertree, Shuffle hypertree, l-Complete binary tree. lh-Coloring Lemma. [6] Let G be a connected graph on n vertices and k be the number of vertices has ∆(G) number of common neighbors. Then h1(G) ≥ ∆(G) + k. Theorem 2.1. [7] Let G be a simple connected graph and H be any induced subgraph of G, then h1(G) ≥ h1(H). Figure 1: Vertex representation of ST (4) Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 214 https://internationalpubls.com 3. Slim Tree The nth slim tree ST (n), n ≥ 2 is recursively defined as follows and is denoted by ST (n) = (V, E, u, l, r), where V is the node set, E is the edge set and u, l, r are vertices addressed as root node, left node and right node respectively. 1. ST (2) is the complete graph K3 with its nodes labeled as u, l and r. 2. The sth slim tree ST (s), with s ≥ 3, is composed of a root node u and two disjoint copies of (s− 1)th slim trees as the left subtree and right sub-tree, denoted by ST l(n−1) = (V1, E1, u1, l1, r1) and ST r(n−1) = (V2, E2, u2, l2, r2), respectively. To be specific, ST (n) = (V, E, u, l, r) is given by V = V1 ∪ V2 ∪ {u}, E = E1 ∪ E2 ∪ {(u, u1), (u, u2), (r1, l2)}, l = l1, r = r2. To simplify our coloring scheme, here the vertices of the slim tree ST (n) are labeled as vij, 1 ≤ i ≤ n, 1 ≤ j ≤ 2i−1, where i represents the level and j represents the position of the vertices at a particular level as shown in Figure 1. In this section we shall prove that ST (n), n ≥ 2 admits locally harmonious coloring. Theorem 3.1. The locally harmonious chromatic number of slim tree network ST (n), n ≥ 2, is given by h1(ST (n)) = 5. Proof. Since ST (2) is the complete graph K3, By lh-Coloring lemma, h1(ST (2)) = ∆ (ST (2)) + 1. For n > 2, we now show that ST (n) cannot be colored with ∆ (ST (n)) + 1 colors with the illustration by considering an induced subgraph ST (3). Without loss of generality, let us color the vertex v21 in ST (3) with the color 1 and denoted by c(v21) = 1. Then its neighboring vertices v11, v31 and v32 can be colored from the set {2, 3, 4} in some order. Again, without loss of generality, assume c(v11) = 2, c(v31) = 3 and c(v32) = 4. It follows, the vertices v33 and v34 can be colored in the following ways: 1. c(v33) = 2 2. c(v34) = 1 or 3. Now, whatever may be the case, since c(v33) = 2, it is easy to see that the vertex v22 is now adjacent with two vertices colored with 2. Therefore, h1(ST (3)) > 4 as shown in Figure 2. By Theorem 2.1, we have h1(ST (n)) ≥ h1(ST (3)) ≥ 5. We now color the vertices of ST (n) level-wise with the color order from left to right repeatedly using the colors from the set {1, 2, 3, 4, 5} as described in Table 1. Table 1: Locally harmonious coloring order of ST (n) S. No. (𝒏 − 𝒊 + 𝟏) (𝒎𝒐𝒅 𝟒) Color order of level i 1 1 < 1, 2, 3, 4, 5 > 2 2 < 4, 1, 3, 5, 2 > 3 3 < 5, 4, 3, 2, 1 > 4 0 < 2, 5, 3, 1, 4 > Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 215 https://internationalpubls.com 2 3 4 2 1 2 3 4 2 3 Figure 2: Illustration for h1(ST (3)) > 4 From the construction of ST (n), it is clear that all levels are independent except the level n. Three adjacent vertices at level i = n have consecutive coloring say k − 1, k, k + 1. Table 1 shows that for the vertex- c o l o r e d k at any level i, 1 ≤ i ≤ n, its neighboring ver- tices receives the distinct colors from the color-set (k + 2), (k + 3), (k + 4), (k + 6), (k + 9) with the numbers taken modulo 5. Therefore, no two incident edges share the same color-pair. By lh-Coloring Lemma, h1(ST (n)) =5. See Figure 3. 2 1 2 3 4 5 1 2 3 Figure 3: h1(ST (4)) = 5 4. Hypertree Definition 4.1. A complete binary tree Tn is the basic scaffolding of a hypertree. Here the vertices of the tree are labeled as 𝑣𝑖𝑗, 0 ≤ i ≤ n, 1 ≤ j ≤ 2n, where i represents the level and j represents the position of vertices of the tree at any level i. The root node receives the label 𝑣01 and the root is said to be at level 0. Horizontal links are added additionally in a hypertree, and two vertices of the tree are united in their own level i if their j’s difference is 2i−1. We denote an n-level hypertree as HT (n). It has 2n+1− vertices and 3(2n − 1) edges. See Figure 4. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 216 https://internationalpubls.com For n ≥ 2, we now propose a locally harmonious coloring algorithm of HT (n). For 2 ≤ i ≤ n, the color order given in the algorithm implies to color the vertices vij from the left to the right repeatedly as construed in Table 2. Algorithm 1 is illustrated in Figure 5. Figure 4: Vertex labeling of HT (3) Table 2: Locally harmonious coloring order of HT (n), n ≥ 2 Proof of Correctness (Algorithm 1): It is to be noted that any vertex v ∈ V (HT (n)) at a particular Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 217 https://internationalpubls.com level i have its neighborhood vertices N (v) in the level i − 1, i, i + 1. Two vertices adjacent at a particular level ‘i’ have consecutive coloring say k and k + 1 or vice versa. From the proposed algorithm, vertices of any three consecutive levels in HT (n) have colored using three distinct color- pairs from the color set {1, 2, 3, 4, 5, 6}. Therefore, for any vertex v ∈ V (HT (n)), the vertices of N [v] receives distinct colors. Thus, the coloring is locally harmonious coloring. 1 1 1 Figure 5: Locally harmonious coloring of HT (3) Theorem 4.2. Let G be the hypertree HT (n), n ≥ 2. Then G admits locally harmonious coloring with the chromatic number h1(G) = 6. Proof. From the proposed algorithm, it is clear that no two adjacent edges share the same color- pair and the number of colors used to color G is 6. Hence, by lh-Coloring Lemma, h1(G) = 6. 5. Shuffle Hypertree Definition 5.1. Shuffle hypertree SHT (n) [8] have been constructed by doing certain modifications in HT (n), which is stated as follows: The deletion of hyper edges in HT (n) and replacing with the new hyper edges (2i + 2k − 1, 2i + 2k) and (2i, 2i+1 − 1) where 1 ≤ i ≤ n, 1 ≤ k ≤ 2i−1 − 1, resulting into a new graph called shuffle hyper tree. It is denoted by SHT (n). It is made up of 2n+1 − 1, 3(2n − 1) vertices and edges respectively. See Figure 6. Figure 6: Vertex representation of SHT (3) 11 12 21 22 v 3 24 31 32 33 34 35 36 37 38 v 01 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 218 https://internationalpubls.com For n ≥ 2, we now propose a locally harmonious coloring algorithm of SHT (n). Color order given in an algorithm have to be color the vertices vij from the left to the right repeatedly in the particular level i using the color in the order as construed in Table 3. Table 3: Locally harmonious coloring order of SHT (n), n ≥ 2 Theorem 5.2. The shuffle hypertree network SHT (n), n ≥ 2 admits locally harmonious coloring with the chromatic number Proof. From the proposed algorithm, it is clear that the number of colors mandatory for solv- ing the locally harmonious coloring problem of SHT (2) is 5. Hence, by lh-Coloring Lemma, h1(SHT (2)) = 5. Similarly, for the case n > 2, we arrive that h1(SHT (n)) = 6. See Figure 7. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 219 https://internationalpubls.com Algorithm 10 is illustrated in Figure 7. Proof of Correctness (Algorithm 10): Two vertices adjacent at a particular level ‘i’ have consecutive coloring say k and k + 1, vise versa. From the proposed algorithm, it is clear that the vertices of any three consecutive levels in SHT (n) have colored using three distinct color- pairs from the color set {1, 2, 3, 4, 5, 6}. Therefore, every color pair of colors is present only once for each edge within distance one of any vertex v ∈ SHT (n). Thus, the coloring is locally harmonious coloring. 1 1 2 Figure 7: h1(SHT (3)) = 6 6. l-Complete Binary Tree Definition 6.1. A graph made up of 2-copies of the complete binary tree Tn, n ≥ 1, say T1, T2 by merging all of the vertices in the last level of T1 with the associated vertex of T2 is called the l-complete binary tree, denoted by l-Tn. The vertices of l-Tn denoted as 𝑣𝑖𝑗 , 0 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 2𝑖 and 𝑣𝑖𝑗 ′, 𝑛 + 1 ≤ 𝑖 ≤ 2𝑛, 1 ≤ 𝑗 ≤ 2(𝑛−𝑖(𝑚𝑜𝑑 𝑛))𝑚𝑜𝑑 𝑛 where i representing a level and j represents the position of a vertex at any particular level i. Formally, we define the vertex set as shown in Figure 8. The l-complete binary tree l-Tn, n ≥ 1, contains 2n−1 number of vertex disjoint copies of C4, where C4 is the cycle on four vertices and the number of vertices in l-Tn is 3.2n−1 − 2, n ≥ 1. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 220 https://internationalpubls.com Figure 8: Vertex labeling of l-T2 Theorem 6.2. Let G be the l-complete binary tree l-Tn, n ≥ 2. Then G admits locally harmonious coloring with the chromatic number h1(G) = 6. Proof. W.l.g, let us color the vertex v01 at the level 0 of G with 1. We shall show that h1(G) = 6 by labeling the vertices vi1 and v ′ Define a labeling function 𝑙 ∶ 𝑣1 𝑖 → {0, 1, 2}, 1 ≤ 𝑖 ≤ 2𝑛 such that 𝑙 (𝑣1 𝑖) = (𝑖 + 1)𝑚𝑜𝑑 3 Depending on the values the vertices of G can be colored level-wise using the color set {1, 2, 3, 4, 5, 6} from the left to the right repeatedly as in the given order construed in Table 4. The vertices in each level are independent and any vertex vij neighborhoods can be found only in the levels i + 1 and i − 1. Since the vertices of any three consecutive levels are colored with 3- different pair of colors {1, 2}, {3, 4} and {5, 6} respectively. By lh-Coloring Lemma, h1(G) = 6. See Figure 9. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 3s (2025) 221 https://internationalpubls.com 7. Concluding Remarks In this paper, we obtained the locally harmonious chromatic number for certain tree-derived net- works which includes slim tree, hypertree, shuffle hypertree and l-complete binary tree. An elegant way of coloring algorithms has been proposed in finding the bounds of these graphs. Locally harmonious chromatic number of other interesting tree derived networks like sierpinski graph, sierpinski gasket, Christmas tree, X-tree are open and under study. References [1] A. Brandstadt, V. D. Chepoi and F. F. Dragan, The algorithmic use of hypertree structure and maximum neighborhood orderings, Discrete Applied Mathematics, 82 (1998) 43–77. [2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to algorithms, MIT press, (1989). [3] W. Gao, Three algorithms for graph locally harmonious coloring, J. Differ. Equ. Appl. 23(1–2) (2015) 8–20. [4] J. L. Gross and J. Yellen, Graph theory and its applications, CRC Press, (2006). [5] J. V. D. Heuvel and M. Johnson, Transversals of subtree hypergraphs and the source location problem in digraphs, Networks, 51(2) (2008) 113–119. [6] J. B. Liu, M. Arockiaraj, A. Nelson, Tight bounds on 1-harmonious coloring of certain graphs, Symmetry, 11(7) (2019) 1–11. [7] A. Nelson, On 1-Harmonious Chromatic Number of Certain Interconnection Networks, Jour- nal of Information and Computational Science, 9(12) (2019) 338-353. [8] D. Paul, I. Rajasingh and R. Sundara Rajan, Acyclic edge-coloring of hypertree and shuffle hypertree, International Journal of Pure and Applied Mathematics, 101(5) (2015) 623-629. [9] D. Paul, I. Rajasingh and R. Sundara Rajan, Tree derived architectures with decycling number equal to cycle packing number, Procedia Computer Science, 57 (2015) 716-726. [10] C. H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Computer Science, 314 (2004) 431-443. [11] Y.L. Wang, T.W. Lin, L.Y. Wang, The local harmonious chromatic problem, Proceedings of the 27th Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, (2010). [12] P. Zhang, A Kaleidoscopic View of Graph Colorings, Springer International Publishing, AG, 2016.