Mathematical Problems of Computer Science 55, 26–34, 2021. UDC 519.1 Some Results on Palette Index of Cartesian Product Graphs Khachik S. Smbatyan Abstract Given a proper edge coloring α of a graph G, we define the palette SG(v, α) of a vertex v ∈ V (G) as the set of all colors appearing on edges incident to v. The palette index š(G) of G is the minimum number of distinct palettes occurring in a proper edge coloring of G. The windmill graph Wd(n, k) is an undirected graph constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kk at a shared universal vertex. In this paper, we determine the bound on the palette index of Cartesian products of complete graphs and simple paths. We also consider the problem of determining the palette index of windmill graphs. In particular, we show that for any positive integers n, k ≥ 2, š(Wd(n, 2k)) = n + 1. Keywords: Edge coloring, Proper edge coloring, Palette, Palette index, Cartesian product, Windmill graph. 1. Introduction Throughout this paper, a graph G always means a finite undirected graph without loops, parallel edges, and it does not contain isolated vertices. Let V (G) and E(G) denote the sets of vertices and edges of a graph G, respectively. The degree of a vertex v in G is denoted by dG(v), and the maximum degree of vertices in G by ∆(G). The terms and concepts that we do not define can be found in [1]. An edge coloring of a graph G is an assignment of colors to the edges of G: it is proper if adjacent edges receive distinct colors. The minimum number of colors required in a proper edge coloring of a graph G is called the chromatic index of G and denoted by χ′(G). By Vizings theorem [9], the chromatic index of G equals either ∆(G) or ∆(G) + 1. A graph with χ′(G) = ∆(G) is called Class 1, while a graph with χ′(G) = ∆(G) + 1 is called Class 2. In this paper, we consider a chromatic parameter called the palette index of a simple graph G. A proper edge-coloring of a graph defines at each vertex v ∈ V (G) the set of colors of its incident edges. That set is called the palette of v and denoted by SG(v, α). The minimum number of palettes, taken over all possible proper edge colorings of a graph G, is called a palette index of a graph and denoted by š(G) [2]. Proper edge colorings with the minimum number of distinct palettes were studied for the first time in 2014, by Horňák, 26 Yerevan State University e-mail: smbatyan1729@gmail.com K. Smbatyan 27 Kalinowski, Meszka, and Woźniak [2]. They determined the palette index of complete graphs. Namely, š(Kn) =   1, if n ≡ 0(mod2) 3, if n ≡ 3(mod4) 4, if n ≡ 1(mod4) (1) Moreover, they also showed that the palette index of a d-regular graph is 1 if and only if the graph is of Class 1. If G is d-regular and of Class 2, then Vizings edge coloring theorem [9] implies that 3 ≤ š(G) ≤ d + 1, and the case š(G) = 2 is not possible, as proved in [2]. There are few results about the palette index of non-regular graphs. Vizings edge coloring theorem also yields an upper bound on the palette index of a graph G with maximum degree ∆ and without isolated vertices, mainly š(G) ≤ 2∆+1 − 2. In [6], Casselgren and Petrosyan provided an improvement and derived the following upper bound on the palette index of bipartite graphs: š(G) ≤ ∑ d∈Deven(G) (⌈∆(G) 2 ⌉ d 2 ) + ∑ d∈Dodd(G) (⌈∆(G) 2 ⌉ d+1 2 ) (d + 1) (2) where Dodd(G) is the set of all odd degrees in G and Deven(G) is the set of even degrees in G. In [3], Bonvicini and Mazzuoccolo proved that if G is 4-regular and of Class 2, then š(G) ∈ {3, 4, 5}, and that all these values are, in fact, attainable. Although it is possible to determine the exact value of the palette index for some classes of graphs, in general, it is an NP-complete problem, because from [4] it is known that computing the chromatic index of a given graph is an NP-complete problem. In this paper, we provide upper and lower bounds on the palette index of Cartesian products of some graphs. We will give the exact number of palettes of Wd(n, 2k) windmill graphs, as well as the upper and lower bounds for Wd(n, 2k + 1). 2. Preliminaries In this section, we introduce some terminology and notation. A matching in a graph G is a set of pairwise independent edges of G. A matching that saturates all the vertices of G is called a perfect matching. Next, we need some additional definitions. Definition 1: (Windmill graph). The windmill graph Wd(n, k) is an undirected graph con- structed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kk at a shared universal vertex. Definition 2: (Cartesian product of graphs). Let G and H be two graphs. The Cartesian product G2H of graphs G and H is a graph such that • the vertex set of G2H is the Cartesian product V (G) × V (H). • two vertices (u, u1) and (v, v1) are adjacent in G2H if and only if either – u = v and u1 is adjacent to v1 in H, or – u1 = v1 and u is adjacent to v in G. 28 Some Results on Palette Index of Cartesian Product Graphs Before we move on, we recall that the Cartesian product graph G2H decomposes into |V (G)| copies of H and |V (H)| copies of G. By the definition of Cartesian products of graphs, G2H has two types of edges: those the vertices of which have the same first coordinate, and those the vertices of which have the same second coordinate. The edges joining vertices with a given value of the first coordinate form a copy of H, so the edges of the first type form nH (|V (G)| = n). Similarly, the edges of the second type form mG (|V (H)| = m), and the union is G2H. Definition 3: Given two graphs G and H, and a vertex y ∈ V (H), the set Gy = {(x, y) ∈ V (G2H)|x ∈ V (G)} is called a G-fiber in the Cartesian product of G and H. For x ∈ V (G), the H-fiber is defined as xH = {(x, y) ∈ V (G2H) | y ∈ V (H)}. G-fibers and H-fibers can be considered as induced subgraphs when appropriate. In [8], authors define the projection to G, which is the map pG : V (G2H) → V (G) is defined by pG(x, y) = x. Also we will need the projection to H; pH : V (G2H) → V (H) is defined by pH(x, y) = y. In the proofs of our results, we also will follow some coloring ideas from [2]. Namely, we will use the coloring ideas described in the proofs of Proposition 5, which states that if k ≥ 0, then š(K4k+3) = 3, and Theorem 7, which shows that if n = 4k + 5, k ̸= 1, then š(Kn) = 4. 3. Main Results First, we will provide some results about the palette index of the Cartesian product of a cycle and simple path. Note that the palette index of Cn2P2 is equal to 1. Clearly, the Cartesian product of those graphs is a Class 1 regular graph and as mentioned above the palette index of Class 1 regular graph is equal to 1. Proposition 1: If n = 2k and m > 2, then š(Cn2Pm) = 2. Proof. First note that Cn2Pm is not a regular graph, hence, š(Cn2Pm) ≥ 2. Let construct a coloring that will induce 2 distinct palettes. Case 1. m is even. Every Cn − fiber can be properly colored alternately with colors a1 and a2. Because of the even length of cycles, we will get exactly one palette, denote it by {a1, a2}. Next, there are n − pieces of Pm − fibers, and every Pm − fiber can be properly colored alternately with colors a3 and a4. As a result, the palette of vertices with degree 3 is {a1, a2, a3}, and the palette of vertices with degree 4 is {a1, a2, a3, a4}. Case 2. m is odd. Suppose that V (Pm) = {v1, v2, ..., vm} and for any i(1 ≤ i ≤ m − 1), vivi+1 ∈ E(Pm). Let α : E(Cn) → {a1, a2} be a proper edge coloring of Cn. Since Cvin , 1 ≤ i ≤ m is isomorphic to Cn; hence, Cvin (4 ≤ i ≤ m) can be properly colored with colors from the color-set {a1, a2}: ∀(u, vi), (u′, vi) ∈ V (Cvin ) if (u, vi)(u′, vi) ∈ E(Cn2Pm), then we define a proper edge coloring γ as follows: γ((u, vi)(u ′, vi)) = α(pG(u, vi)pG(u ′, vi)) = α(uu ′) = a, where a ∈ {a1, a2}. Afterwards, the fibers Cv1n , Cv2n and Cv3n can be colored alternately with colors from the color-sets {a1, a2}, {a1, a4} and {a1, a3}, respectively. Then we will color the edges joining Cv1n to C v2 n and C v2 n to C v3 n by the colors a3 and a2, respectively. Observe K. Smbatyan 29 that the remaining uncolored edges of Pm − fibers can be properly colored alternately with colors a3 and a4; the obtained coloring γ is a proper edge coloring of Cn2Pm with a minimum number of palettes. Using the same ideas makes it easy to obtain a coloring for C2n+12P2m, inducing 2 distinct palettes. When the number of vertices of the cycle and the number of vertices of the path are odd, we have the following theorem. Theorem 1: If n = 2k1 + 1 and m = 2k2 + 1, k1, k2 > 0, then š(Cn2Pm) = 4. Proof. Suppose that V (Pm) = {v1, v2, ..., vm} and dPm(v1) = dPm(vm) = 1 and α is a coloring of Cn2Pm inducing š(Cn2Pm) distinct palettes. Let show that the value of the palette index is at least 4. Case 1. š(Cn2Pm) = 1. It follows that the graph is a regular graph, which is a contra- diction. Case 2. š(Cn2Pm) = 2. Denote by P1 and P2 palettes induced by α. Clearly, P1∩P2 ̸= ∅, therefore there is a color a ∈ P1 ∩P2 so that the edges colored with a form a perfect matching of the graph. However, |V (Cn2Pm)| is an odd number, which means that the graph cannot have a perfect matching, a contradiction. Case 3. š(Cn2Pm) = 3. Denote by P1, P2, and P3 palettes induced by α. Suppose that |P1| = |P2| = 3 and |P3| = 4. Clearly, there is no color belonging to all three palettes. Indeed, otherwise, that color would induce a perfect matching of Cn2Pm, which is impossible. Assume that (P1 ∪ P2) \ P3 ̸= ∅, then there is a color a ∈ P1 ∪ P2 such that the edges colored with a form a perfect matching for Cn, which is impossible too, but this also means that the set P1 ∩ P2 ∩ P3 cannot be empty, a contradiction. Now, suppose that |P1| = |P2| = 4 and |P3| = 3. Clearly there is a color a ∈ P1 ∩ P2 and a /∈ P3. This implies that the edges colored with a form a perfect matching of Cn−22Pm, which is impossible. Hence, š(Cn2Pm) ≥ 4. Next, we need to show the existence of a proper edge coloring α inducing four palettes. Assume that β is a proper edge coloring of Cn with colors from color-set S = {a1, a2, a3}, inducing 3 distinct palettes. As we have already mentioned, Cvin , 1 ≤ i ≤ m − 1 can be properly colored with colors from the color-set S. Then for all i(1 ≤ i ≤ m − 1) the edge that joins (u, vi) ∈ V (Cvin ) and (u, vi+1) ∈ V (Cvi+1n ) will be colored in one of the two ways, first if there is a color a ∈ S that a does not belong to color-sets assigned to the incident edges of (u, vi) and (u, vi+1), then that edge will be colored with a. Otherwise it will be colored with a new color a4 /∈ S. Thereby we constructed coloring of the subgraph of Cn2Pm, that is isomorphic to Cn2Pm−1, inducing two palettes {a1, a2, a3} and {a1, a2, a3, a4}. Note that the palette of the vertices of Cvm−1n is {a1, a2, a3}; hence, the colors as- signed to the edges of Cvm−1n divide that edge set into three disjoint sets: two sets X and Y , each having n−1 2 elements, and one one-element set, say {(u, vm−1)(u1, vm−1)}. With- out loss of generality, we may suppose that (u, vm−1)(u2, vm−1) ∈ Y and X, Y are the sets of edges colored with a1 and a2, respectively. For all (u ′, vm−1)(u ′′, vm−1) ∈ X let do the following changes: α((u′, vm−1)(u ′′, vm−1)) = a4, α((u ′, vm−1)(u ′, vm)) = a2 and α((u′′, vm−1)(u ′′, vm)) = a2. Since (u, vm−1) is the only vertex that the recent changes did not affect, α((u, vm−1)(u, vm)) = a4. Finally, coloring the edge α((u, vm)(u1, vm)) = a5 and the remaining uncolored edges alternately with colors a2 and a3 will induce two new palettes; hence, š(Cn2Pm) = 4. 30 Some Results on Palette Index of Cartesian Product Graphs Next, we will examine the palette index of the Cartesian product of complete graphs and paths. Complete graph K2k is of Class 1 and š(K2k) = 1, therefore š(K2k2P2) = 1. On the other hand, the minimum coloring of K2k+1 induces 2k + 1 distinct palettes. Indeed, each palette has 2k colors. This means that exactly one color is missing at each vertex. So we can use the minimum coloring of Kn for all Kn − fibers and color the edges joining them with missing colors, hence, š(K2k+12P2) = 1. Corollary 1. If n > 2 and m > 2, then š(K2n2Pm) = 2. Proof. Construction of a proper edge coloring of K2n2Pm is very similar to the steps that we have already described in Proposition 1, the single difference being that in this case we will color Kn − fibers with the minimum coloring described above. Theorem 2: For any odd positive integers m and k ≥ 0, we have š(K4k+32Pm) = 4. Proof. Let V (Pm) = {v1, v2, ..., vm} and dPm(v1) = dPm(vm) = 1. As we have already mentioned above there is a proper edge coloring with a minimum number of distinct palettes α : E(K4k+3) → S = {a1, a2, a3, ...a4k+3} inducing 4k+3 different palettes. We will construct the coloring γ for K4k+32Pm as follows; ∀i(1 ≤ i ≤ m − 1) and ∀(u, vi)(u′, vi) ∈ E(Kvi4k+3) γ((u, vi)(u ′, vi)) will be set equal to α(uu ′). Note that for any i(1 ≤ i ≤ m − 1), the vertices (u, vi) and (u, vi+1) are joined with the edges of Pm −fibers, and we have two possible cases for the coloring of these edges; • if S \ SK4k+32Pm((u, vi)) = {a}, then γ((u, vi)(u, vi+1)) = a. • if S \ SK4k+32Pm((u, vi)) = ∅, then γ((u, vi)(u, vi+1)) = b, b /∈ S. Note that the fiber K vm−1 4k+3 always has more than k + 1 edges colored with the same color. Assume that M = {(ui1, vm−1)(ui2, vm−1), ..., (ui2k+1, vm−1)(ui2k+2, vm−1)} is the set of edges colored with a′ ∈ S. Now let recolor some edges. For any j(1 ≤ j ≤ k + 1); γ((ui2j−1, vm−1)(ui2j, vm−1)) = b, γ((uis, vm−1)(uis, vm)) = a ′, ∀s ∈ {1, 2, ..., 2k + 2}, γ((ui, vm−1)(ui, vm)) = b, ∀ui ∈ V (K vm−1 4k+3 ) \ {ui1, ui2, ..., ui2k+2} To color the edges of Kvm4k+3, we will follow the coloring idea introduced in the proof of [2](Proposition 5). Using the color-set S ∪ {b1, b2, ...b2k+1} ∪ {b} and taking the vertex set X = {ui1, ui2, ..., ui2k}, Y = V (K vm n ) \ (X ∪ {ui2k+1}) and one-element set {ui2k+1} will let us obtain coloring that induces 2 new palettes. Clearly, we can make the palette of the vertices from the vertex set X equal to {a1, a2, a3, ...a4k+3}, causing new palettes only on the vertices from the vertex set Y and {ui2k+1}; hence š(K4k+32Pm) ≤ 4. Now let us show that the palette index is at least 4. Suppose first that š(K4k+32Pm) = 3, and let α be the corresponding coloring of K4k+32Pm. Denote by P1, P2 and P3 the palettes caused by α. Let Vi = {x ∈ V : S(x, α) = Pi}, i = 1, 2, 3. First, there is no color belonging to all three palettes, otherwise this color would induce a perfect matching of K4k+32Pm, which is impossible. K. Smbatyan 31 Case 1. |P1| = |P2| = n, |P3| = n + 1. Note that (P1 ∪ P2) \ P3 = ∅; otherwise there is a color a ∈ (P1 ∪ P2) \ P3 then the edges colored with a form a perfect matching of Kn, which is impossible. It follows that P1 ∩ P2 ∩ P3 ̸= ∅, a contradiction. Case 2. |P1| = |P2| = n + 1, |P3| = n. Clearly, there is an edge e ∈ E(K4k+32Pm, ) joining V1 and V2. Assume that α(e) /∈ P3, then the edges colored with α(e) will form a perfect matching of K4k+12Pm, which is a contradiction. Suppose next that š(K4k+32Pm) = 2, the intersection of the induced palettes similarly cannot be an empty set. Hence, š(K4k+32Pm) ̸= 2. Also, note that constructed coloring will induce at most 5 palettes for K4k+52P2m+1, the single difference being that in this case we will color the fiber Kvm4k+5 using the coloring constructed in the proof of [2](Theorem 7). Corollary 2. If k ≥ 0 and m ≥ 1, then 4 ≤ š(K4k+52P2m+1) ≤ 5 Next results are about the palette index of windmill graphs. Fig. 1. Wd(2, 6) graph coloring. Proposition 2: If n, k ≥ 2, then š(Wd(n, k)) ≥ n + 1. Proof. Suppose that š(Wd(n, k)) = m (m < n + 1). There is a proper edge coloring of Wd(n, k) inducing m distinct palettes Pi, i = 1, 2, ..., m. Let Vi be the set of all vertices of Kn with palette Pi and let ni = |Vi|, i = 1, 2, ..., m. Without loss of generality, suppose that |Vm| = nm = 1 is a one-element set, say {u}. Assume that u is the shared vertex of 32 Some Results on Palette Index of Cartesian Product Graphs Wd(n, k). Clearly, ∑m i=1 ni = |V (Wd(n, k))| = n(k −1)+1. This implies that ∃i(1 ≤ i ≤ m) that ni ≥ k. Indeed, if ni < k(1 ≤ i ≤ m), then it follows; m∑ i=1 ni = m−1∑ i=1 ni + 1 ≤ (m − 1)(k − 1) + 1 < n(k − 1) + 1 = |V (Wd(n, k))|, which is impossible. Thus, ∃j such that |Vj| = nj > k. For any vertex of Vj there is an edge joining it with shared vertex u, and the number of such edges is equal to nj. On the other hand, nj > |Pj| = k − 1, which is a contradiction; therefore š(Wd(n, k)) ≥ n + 1. At the same time the upper bound of the palette index of windmill graphs depends on the number of complete graphs. Theorem 3: For any positive integers n, k ≥ 2, we have š(Wd(n, 2k)) = n + 1. Proof. We only need to show the existence of a coloring α inducing n+1 palette. Denote by u the shared vertex of Wd(n, 2k). Note that Wd(n, 2k) − u is a graph that consists of n components, and every component is a complete graph with 2k − 1 vertices. For every K2k−1 complete graph exists coloring inducing 2k − 1 palettes, and at each vertex, exactly one color is missing, which will be assigned to the edge joining that vertex and the shared vertex u. Clearly, this coloring will induce exactly one palette on every odd component, and as a result, we will construct coloring α that will induce n + 1 distinct palettes. Fig.1 shows the proper edge coloring α of the graph Wd(2, 6) inducing 3 distinct palettes. We will also give an upper bound for the palette index of Wd(n, k) for any k odd number. Corollary 3. For any positive integers k, n ≥ 2, we have š(Wd(n, k)) ≤ { 2n + 1, if k ≡ 3 (mod 4), 3n + 1, if k ≡ 1 (mod 4). (3) Proof. Suppose that Kik (1 ≤ i ≤ n) are the copies of the complete graph in Wd(n, k), and u is the shared universal vertex. Denote by C1, C2, ..., Cn disjoint color-sets needed for a proper edge coloring of a complete graph that induces a minimum number of distinct palettes. Case 1. k ≡ 3 (mod 4). We will use the coloring described in the proof of [2](Proposition 5). Assume that ∀i(1 ≤ i ≤ n) αi is a proper edge coloring of Kik with color-set Ci inducing 3 distinct palettes. While constructing the αi coloring, the complete graph’s vertex set is partitioned into three sets. One of these sets is a one-element set, which induces a new unique palette. Taking {u} as that set for any partition of V (Kik)(1 ≤ i ≤ n) will let us obtain coloring of Wd(n, k) that induces at most 2n + 1 distinct palettes. Case 2. k ≡ 1 (mod 4). We will use the coloring described in the proof of [2](Theorem 7). Assume that ∀i(1 ≤ i ≤ n) αi is a proper edge coloring of Kik with color-set Ci inducing 4 distinct palettes. In this case, coloring αi also causes a new unique palette on the vertex of one-element set. Similar to the previous case, taking {u} as that set for all partitions of V (Kik) (1 ≤ i ≤ n) will let us obtain coloring of Wd(n, k) that induces 3n + 1 distinct palettes. K. Smbatyan 33 4. Conclusion In the current article we examined the palette index of Cartesian products of graphs. Namely, we determined the palette index of the Cartesian product of cycles and paths and constructed colorings based on the length of the cycle, inducing a minimum number of palettes. Next, we gave some results connected to the palette index of the Cartesian product of complete graphs and paths. We also considered the problem of determining the palette index of windmill graphs. In particular, we showed the existence of coloring α, such that the number of palettes of Wd(n, 2k) for any n, k ≥ 2 induced by α is equal to n + 1. Moreover, we determined the upper bounds for the windmill graphs in case when the number of vertices of each complete graph is odd. References [1] D.B. West, Introduction to Graph Theory, N.J.: Prentice-Hall, 2001. [2] M. Horňák, R. Kalinowski, M. Meszka and M. Woźniak, “Minimum number of palettes in edge colorings“, Graphs and Combinatorics, vol. 30, pp. 619–626, 2014. [3] S. Bonvicini and G. Mazzuoccolo, “Edge-colorings of 4-regular graphs with the mini- mum number of palettes“, Graphs and Combinatorics, vol. 32, pp. 1293–1311, 2016. [4] I. Holyer, “The NP-completeness of edge-coloring“, SIAM Journal on Computing, vol. 10, pp. 718–720, 1981. [5] M. Avesani, A. Bonisoli and G. Mazzuoccolo, “A family of multigraphs with large palette index“, Ars Mathematica Contemporanea, vol. 17, pp. 115–124, 2019. [6] C. J. Casselgren and P. A. Petrosyan, “Some results on the palette index of graphs“, Discrete Mathematics and Theoretical Computer Science, vol. 21, no. 3. [7] S. Fiorini and R.J. Wilson, “Edge-Colorings of Graphs“, Research Notes in Mathemat- ics, vol. 16, Pitman, London, UK, 1977. [8] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs Second Edition, CRC Press, 2011. [9] V. G. Vizing, “On an estimate of the chromatic class of a p-graph“, Diskret. Analiz 3, pp. 25–30, 1964. Submitted 14.02.2021, accepted 08.05.2021. 3 4 Some Results on Palette Index of Cartesian Product Graphs àñáß ³ñ¹ÛáõÝùÝ»ñ ·ñ³ýÝ»ñÇ ¹»Ï³ñïÛ³Ý ³ñï³¹ñÛ³ÉÝ»ñÇ å³ÉÇïñ³ÛÇ Çݹ»ùëÇ Ù³ëÇÝ Ê³ãÇÏ ê. êÙµ³ïÛ³Ý ºñ¨³ÝÇ å»ï³Ï³Ý ѳٳÉë³ñ³Ý e-mail: smbatyan1729@gmail.com ²Ù÷á÷áõÙ îñí³Í ¿ ·ñ³ýÇ ®-×Çßï ÏáÕ³ÛÇÝ Ý»ñÏáõÙ, SG ( v; ® ) -áí Ý߳ݳÏáõÙ »Ý v 2 V ( G ) ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÇ µ³½ÙáõÃÛáõÝÁ: G ×Çßï ÏáÕ³ÛÇÝ Ý»ñÏÙ³Ý ¹»åùáõÙ Çñ³ñÇó ï³ñµ»ñ å³ÉÇïñ³Ý»ñÇ Ýí³½³·áõÛÝ ù³Ý³ÏÁ ³Ýí³ÝáõÙ »Ý G- Ç å³ÉÇïñ³ÛÇÝ Çݹ»ùë ¨ Ý߳ݳÏáõÙ ·s( G) -áí: W d( n; k ) -Ý ãáõÕÕáñ¹í³Í ·ñ³ý ¿, áñÁ ϳéáõóíáõÙ ¿ k ¸ 2 »í n ¸ 2 ³ñÅ»ùÝ»ñÇ Ñ³Ù³ñ n ѳï Kk ÉñÇí ·ñ³ýÝ»ñÇ Ù»Ï ÁݹѳÝáõñ ·³·³ÃáõÙ ÙdzíáñÙ³Ý ÙÇçáóáí: ²Ûë Ñá¹í³ÍáõÙ Ù»Ýù Ïï³Ýù å³ÉÇïñ³ÛÇÝ Çݹ»ùëÇ ·Ý³Ñ³ï³ÏÝ ÉñÇí ·ñ³ýÇ »í å³ñ½ ׳ݳå³ñÑÇ ¹»Ï³ñ¹Û³Ý ³ñï³¹ñÛ³ÉÇ Ñ³Ù³ñ: Ø»Ýù ݳ¨ ïí»É »Ýù å³ÉÇïñ³ÛÇÝ Çݹ»ùëÇ í»ñÇÝ ·Ý³Ñ³ï³Ï³ÝÁ W d ( n; k ) -Ç Ñ³Ù³ñ: سëݳíáñ³å»ë, óáõÛó ¿ ïñí»É, áñ Ï³Ù³Û³Ï³Ý k ¸ 2 »í n ¸ 2 ½áõÛ· ³ÙµáÕç Ãí»ñÇ Ñ³Ù³ñ ·s( W d( n; 2 k ) ) = n + 1 : Íåêîòîðûå ðåçóëüòàòû îá èíäåêñå ïàëèòðû äåêàðòîâî ïðîèçâåäåíèå ãðàôîâ Õà÷èê Ñ. Ñìáàòÿí Åðåâàíñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò e-mail: smbatyan1729@gmail.com Àííîòàöèÿ Ïðè ïðàâèëüíîé ®-ðåáåðíîé ðàñêðàñêå ãðàôà G ìû îïðåäåëÿåì ïàëèòðó SG ( v; ®) âåðøèíû v 2 V ( G) êàê ìíîæåñòâî âñåõ öâåòîâ, ïîÿâëÿþùèõñÿ íà ðåáðàõ, ñìåæíûõ ñ v Èíäåêñ ïàëèòðû ·s( G ) ãðàôà G ÿâëÿåòñÿ ìèíèìàëüíûì ÷èñëîì ðàçëè÷íûõ ïàëèòð, âñòðå÷àþùèõñÿ ïðè âñåõ ïðàâèëüíûõ ðåáåðíûõ ðàñêðàñêàõ G.  òåîðèè ãðàôîâ ìåëüíèöà W d ( n; k ) - ýòî íåîðèåíòèðîâàííûé ãðàô, ïîñòðîåííûé äëÿ k ¸ 2 è n · 2 ïóò¸ì ïðåäïðèÿòèé n êîïèè ïîëíûõ ãðàôîâ Kk â îäíîé îáùåé âåðøèíå  ýòîé ñòàòüå ìû äàåì îöåíêó èíäåêñà ïàëèòðû äåêàðòîâîãî ïðîèçâåäåíèÿ ïîëíûõ ãðàôîâ è ïðîñòûõ ïóòåé. Ìû òàêæå ðàññìàòðèâàåì çàäà÷ó îïðåäåëåíèÿ èíäåêñà ïàëèòðû ãðàôîâ ìåëüíèö.  ÷àñòíîñòè, ìû ïîêàçûâàåì, ÷òî äëÿ ëþáûõ ïîëîæèòåëüíûõ öåëûõ ÷èñåë k ¸ 2 è n · 2 , ·s( W d ( n; 2 k ) ) = n + 1 . Êëþ÷åâûå ñëîâà: ðåáåðíàÿ ðàñêðàñêà, ïðàâèëüíàÿ ð¸áåðíàÿ, ðàñêðàñêà, ïàëèòðà, èíäåêñ ïàëèòðû, äåêàðòîâî ïðîèçâåäåíèå, ãðàô ìåëüíèöà. ´³Ý³ÉÇ µ³é»ñ՝ ÎáÕ³ÛÇÝ Ý»ñÏáõÙ, ×Çßï ÏáÕ³ÛÇÝ Ý»ñÏáõÙ, å³ÉÇïñ³, å³ÉÇïñ³ÛÇ Çݹ»ùë, ¸»Ï³ñïÛ³Ý ³ñï³¹ñÛ³É: 02_Khachik_Smbatyan_MPCS_55 02