Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 1194 https://internationalpubls.com Results on Grundy Number of Fan Graph Families K. Annathurai1, P. Periasamy, V. Sankar Raj3 1 Department of Mathematics, Thiruvalluvar College, Papanasam - 627425, Tamil Nadu, India. Email: kannathuraitvcmaths@gmail.com 2 Department of Mathematics, Research Scholar, Register Number 21124012091019, Manonmaniam Sundaranar University, Tirunelveli - 627012, Tamilnadu, India. Email: ppskmttc2013@gmail.com 3 Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli – 627012, Tamilnadu, India. Email: sankarrajv@gmail.com Article History: Received:01/10/2024 Revised: 06/11/2024 Accepted: 30/12/2024 1 Introduction Abstract: A Grundy k−coloring of a graph G is a proper k−coloring of vertices in G using colors {1, 2, · · · , k} such that for any two colors i and j, i < j, any vertex colored j is adjacent to some vertex colored i. The First-Fit or Grundy chromatic number (or simply Grundy number) of a graph G, denoted by Γ (G), is the largest integer k, such that there exists a Grundy k−coloring for G. It can be easily seen thatΓ (G) equals to the maximum number of colors used by the greedy (or First-Fit) coloring of G . In this paper, we obtain the grundy chromatic number of fan graph, line graph of fan graph, middle graph of fan graph and total graph of fan graph. Keywords: Grundy chromatic number, Fan graph, line graph, middle graph, Total graph. The notion of Grundy colorings was introduced by Patrick Michael Grundy in 1939. Author has dealing with combinatorial games contained ideas that led to the concept of Grundy colorings of graphs. A Grundy coloring [4, 6, 16] of a graph G is a proper vertex coloring of G (whose colors, as usual, are positive integers) having the property that for every two colors i and j with i < j, every vertex colored j has a neighbor colored i. Consequently, every Grundy coloring is a complete coloring. The 4-coloring of the tree T1 of Figure 1 is a Grundy 4-coloring and is therefore a complete 4-coloring as well. However, the complete 3-coloring of T2 shown in Figure 1.1 is not a Grundy 3-coloring. Recall that a greedy coloring [1] c of a graph G is obtained from an ordering φ : v1, v2, · · · , vn of the vertices of G in some manner, by defining c(v1) = 1, and Figure 1.1: Complete and Grundy colorings mailto:kannathuraitvcmaths@gmail.com mailto:ppskmttc2013@gmail.com mailto:sankarrajv@gmail.com Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 1195 https://internationalpubls.com once colors have been assigned to V1, V2, · · · , Vp for some integer p with 1 ≤ p ≤ n, c(Vp+1) is defined as the smallest color not assigned to any neighbor of Vp+1 belonging to the set {V1, V2, · · · , Vp}. The coloring c so produced is then a Grundy coloring of G. (i.e.), every greedy coloring is a Grundy coloring. The maximum positive integer k for which a graph G has a Grundy k-coloring is denoted by Γ(G) and is called the Grundy chromatic number of G or more simply the Grundy number of G. If the Grundy number of a graph G is k, then in any Grundy k-coloring of G (using the colors 1, 2, · · · , k), every vertex v of G colored k must be adjacent to a vertex colored i for each integer i with 1 ≤ i ≤ k. Thus ∆(G) ≥ deg(v) ≥ (k − 1) and so Γ(G) ≤ ∆(G) + 1 (1) for every graph G. Since every Grundy coloring of a graph G is a proper coloring, it follows that, χ(G) ≤ Γ(G). The Grundy number of a graph was perhaps introduced for the first time by Christen and Selkow [2]. In [3], Erd¨os et., al. proved that the Grundy number of a graph is in fact the same as a chromatic number of a graph which was defined and studied independently by Simmons [12]. In [8] the authors studied the Grundy number of hypercubes and determined the exact values. From computational point of view, polynomial time algorithms for determining the Grundy number have been given for trees in [7] and for partial k-trees in [13]. In a manuscript [5] the NP-completeness of determining the Grundy number of general graphs has been proved. Therefore, they gave an affirmative answer to the problem 10.4 posed in the graph coloring problem book [9] which asks whether determining the Grundy chromatic number of graphs is an NP-complete problem. 2 Preliminaries All graphs we consider are simple and fnite. Definition 2.1 The generalized fan graph Fn,m is defined as the graph join Kn+Pm, where Kn is the empty graph with n vertices and Pm is the path graph with m vertices. The case n = 1 corresponds to the usual Fan Graphs, while n = 2 corresponds to the Double Fan graphs, etc. Number of edges of the Generalized Fan graph Fn,m with (n + m) vertices is nm + (m − 1). Definition 2.2 The line graph of G denoted by L(G) is the graph with vertices are the edges of G with two vertices of L(G) adjacent whenever the corresponding edges of G are adjacent. Definition 2.3 Middle graph M(G) of a graph G is defined with the vertex set V (G) ∪ E(G), in which two elements are adjacent if and only if either both are adjacent edges in G or one of the elements is a vertex and the other one is an edge incident to the vertex in G. Definition 2.4 Total graph T(G) of a graph G defined with the vertex set V (G) ∪ E(G), in which two elements are adjacent if and only if one of the following holds true (i) both are adjacent edges or vertices in G (ii) one is a vertex and other is an edge incident to it in G. 3 Main Results We begin by presenting the existing results concerning the grundy chromatic number of fan graph, line graph of fan graph, central graph of fan graph, middle graph of fan graph and total graph of fan graph. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 1196 https://internationalpubls.com Theorem 3.1 For any positive integer m and n ≥ 2, then Γ(Fm,n) is 3, if n = 2, 3 and is 4, if n ≥ 4. Proof: Let us consider the Fan Graph of the form Fm,n, where m ≥ 1 and n ≥ 2. The Grundy chromatic number of Fm,n be denoted as Γ(Fm,n). Let V(Fm,n) represent the vertices of Fm,n. That is, V(Fm,n) is Ui (1 ≤ i ≤ m) and Vj (1 ≤ j ≤ n). We define a mapping, σ : V (Fm,n) → N as follows: Case (i): For n = 2, 3. For 1 ≤ i ≤ m, 1 ≤ j ≤ 3, σ (Ui) = 3. σ (vj ) = 1, if j ≡ 1 mod 2 and 2, if j ≡ 0 mod 2 Since Γ(Fn,m) ≤ 3. Assume that Γ(Fn,m) > 3. For n = 2, there exist a clique of order 3. It is obviously the color is 3. For n = 3, Suppose, the vertices Ui (1 ≤ i ≤ m) received any one of the color 1 to 4 and remaining three color are assigned to the vertices Vj (1 ≤ j ≤ 3). This arises a contradiction of grundy chromatic number definition. Hence Γ(Fm,n) ≤ 3. Therefore, Γ(Fm,n) = 3, (m ≥ 1; 2 ≤ n ≤ 3). Case (ii): For n ≥ 4. For 1 ≤ i ≤ m, σ (Ui) = 4. Subcase (i): For n ≡ 0 mod 3. σ (Vj ) = (For 1 ≤ j ≤ n − 2 ) 1, if j ≡ 1 mod 3 3, if j ≡ 2 mod 3 and 2, if j ≡ 0 mod 3 σ (Vn−1) = 2; σ (Vn) = 1. Subcase (ii): For n ≡ 2 mod 3. σ (Vj ) = (For 1 ≤ j ≤ n – 1) 1, if j ≡ 1 mod 3 3, if j ≡ 2 mod 3 and 2, if j ≡ 0 mod 3 σ (Vn) = 2. Subcase (iii): For n ≡ 1 mod 3. σ (vj ) = (For 1 ≤ j ≤ n) 1, if j ≡ 1 mod 3 3, if j ≡ 2 mod 3 and 2, if j ≡ 0 mod 3 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 1197 https://internationalpubls.com Since Γ(Fn,m) ≤ 4. Assume that Γ(Fn,m) > 4, Suppose, the vertices Ui (1 ≤ i ≤ m) received any one of the color 1 to 5 and remaining four color are assigned to the vertices vj (1 ≤ j ≤ n). This arises a contradiction of grundy chromatic number definition. Hence Γ(Fm,n) ≤ 4. Therefore, Γ(Fm,n) = 4, n ≥ 4. Theorem 3.2 For any positive integer m and n ≥ 3, then Γ [L(Fm,n)] = n + 1, n ≥ m. Proof: Let us consider the Fan Graph of the form Fm,n, where m ≥ 1 and n ≥ 3. Let V (Fm,n) = {Ui : 1 ≤ i ≤ m} ∪ {vj : 1 ≤ j ≤ n} represent the vertices of Fm,n. By the definition of line graph, let V [L(Fm,n)] = Sum i=1 to m {ei,j : 1 ≤ j ≤ n} ∪ {Xj,j+1 : 1 ≤ j ≤ n − 1}. We define a mapping, σ : V [L(Fm,n)] → N as follows: For 1 ≤ i ≤ m, 1 ≤ j ≤ n, σ (ei,j ) = i + j, i ≡ i mod m; j ≡ j mod n σ (ej,j+1) = 1, 1 ≤ j ≤ n − 1. Since above color partition Γ(Fn,m) ≤ n + 1. Assume that Γ(Fn,m) > n + 1. Since there exist a clique of order n. By the above Equation Γ [L(Fm,n)] ≤ n + 1. This arises a contradiction. Therefore, Γ [L(Fm,n)] = n + 1. Theorem 3.3 For any positive integer m and n ≥ 3, then Γ [M (Fm,n)] = n + 2, n ≥ m. Proof: Let us consider the Fan Graph of the form Fm,n, where m ≥ 1 and n ≥ 3. Let V (Fm,n) = {Ui : 1 ≤ i ≤ m} ∪ {Vj : 1 ≤ j ≤ n} represent the vertices of Fm,n. By the definition of middle graph, let V [M (Fm,n)] = V (Fm,n) ∪ Sum i=1 to m {ei,j : 1 ≤ j ≤ n} ∪ {xj,j+1 : 1 ≤ j ≤ n−1}. We define a mapping, σ : V [M (Fm,n)] → N as follows: For 1 ≤ i ≤ m, 1 ≤ j ≤ n, σ (ei,j ) = i + j + 1, i ≡ i mod m; j ≡ j mod n σ (Ui) = 1; Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 1198 https://internationalpubls.com σ (Vj ) = 2; σ (ej,j+1) = 1, 1 ≤ j ≤ n − 1. Since above color partition Γ(Fn,m) ≤ n + 2. Assume that Γ(Fn,m) > n + 2. Since there exist a clique of order n + 1. By Equation (1), Γ [M (Fm,n)] ≤ n + 2. This arises a contradiction. Therefore, Γ [M (Fm,n)] = n + 2. Theorem 3.4 For any positive integer m and n ≥ 3, then Γ [T (Fm,n)] = n + 2, n ≥ m. Proof: Let us consider the Fan Graph of the form Fm,n, where m ≥ 1 and n ≥ 3. Let V (Fm,n) = {Ui : 1 ≤ i ≤ m} ∪ {vj : 1 ≤ j ≤ n} represent the vertices of Fm,n. By the definition of total graph, let V [T (Fm,n)] = V (Fm,n) ∪ Sum i=1 to m {ei,j : 1 ≤ j ≤ n} ∪ {xj,j+1 : 1 ≤ j ≤ n − 1}. We define a mapping, σ : V [T (Fm,n)] → N as follows: For 1 ≤ i ≤ m, 1 ≤ j ≤ n, σ (ei,j ) = i + j + 1, i ≡ i mod m; j ≡ j mod n σ (Ui) = 1; σ (Vj ) = 2; σ (ej,j+1) = 1, 1 ≤ j ≤ n − 1. Since the above color partition Γ(Fn,m) ≤ n+2. Assume that Γ(Fn,m) > n+2. Since there exist a clique of order n + 1. Γ [T (Fm,n)] ≤ n + 2. This arises a contradiction. Therefore, Γ [T (Fm,n)] = n + 2. Conclusion In this paper we discussed about the grundy chromatic number of fan graph, line graph of fan graph, middle graph of fan graph and total graph of fan graph. This paper motivates the reader to do further research in grundy coloring of some other graphs and also other colorings of different types of graphs. References [1] Y. Caro, A. Seb¨o, M. Tarsi, Recognizing greedy structures, J. Algorithms 20 (1996) 137- 156. [2] C.A. Christen, S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory Ser. B 27 (1979) 49-59. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 8s (2024) 1199 https://internationalpubls.com [3] P. Erd¨os, W.R. Hare, S.T. Hedetniemi, R. Laskar, On the equality of Grundy and ochromatic number of graphs, J. Graph Theory 11 (1987), 157-159. [4] Z. F¨uredi, A. Gy´arf´as, G. S´ark¨ozy, S. Selkow, Inequalities for the First-Fit chromatic number, 59(1), (2008), 75-88. [5] N. Goyal, S. Vishvanathan, NP-completeness of undirected Grundy numbering and related problems, Manuscript, Bombay, 1997. [6] A. Gy´arf´as, J. Lehel, On-line and first-fit coloring of graphs, J. Graph Theory 12 (1988) 217-227. [7] S.M. Hedetniemi, S.T. Hedetniemi, A. Beyer, A linear algorithm for the Grundy (coloring) number of a tree, Congr. Numer. 36 (1982), 351-363. [8] D.G. Hoffman, P.D. Johnson Jr., Greedy colorings and the Grundy chromatic number of the n-cube, Bull. ICA 26 (1999) 49-57. [9] T.R. Jensen, B. Toft, Graph Coloring Problems,Wiley, NewYork, 1995. [10] K Kaliraj, VJ Vernold, On equitable coloring of Helm graph and Gear graph, International Journal of Mathematical Combinatorics, Vol.4 (2010), 32-37. [11] K. Kaliraj, J. Vernold Vivin and M.M. Akbar Ali, On Equitable Coloring of Sun let Graph Families, Vol.CIII (2012), 497-504. [12] G.J. Simmons, On the ochromatic number of a graph, Congr. Numer. 40 (1983) 339-366. [13] J.A. Telle, A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550. [14] M. Venkatachalam, J. Vernold Vivin and K. Kaliraj, Harmonious Coloring on Double Star Graph Families, 43(2) (2012), 153-158. doi:10.5556/j.tkjm.43.2012.153-158. [15] J. V. Vivin, K Kaliraj, On equitable coloring of corona of wheels, Electronic Journal of Graph Theory and Applications, 4 (2), 206-222. [16] M. Zaker, Grundy chromatic number of the complement of bipartite graphs, Australas. J. Combin. 31 (2005) 325-329. [17] Harishchandra Patel, “Impedance Control in HDI and Substrate-Like PCBs for AI Hardware Applications” (2024). Journal of Electrical Systems, 20(11s), 5109-5115.