Cohen-Macaulayness of powers of edge ideals of edge-weighted graphs Thanks: ∗ Corresponding author Thanks: 2020 Mathematics Subject Classification . Primary 13C15, 13C14; Secondary 05E40, 13F20 Thanks: Keywords: Cohen-Macaulayness, powers of the edge ideal, the edge-weighted graph, very well-covered graph, weighted tree Jiaxin Li, Tran Nam Trung, Guangjun Zhu ∗ Abstract . In this paper, we characterize the Cohen-Macaulayness of the second power I ​ ( G ω ) 2 I(G_{\omega})^{2} of the weighted edge ideal I ⁡ ( G ω ) I(G_{\omega}) when the underlying graph G G is a very well-covered graph. We also characterize the Cohen-Macaulayness of all ordinary powers of I ​ ( G ω ) n I(G_{\omega})^{n} when G G is a tree with a perfect matching consisting of pendant edges and the induced subgraph G ⁡ [ V ⁡ ( G ) ∖ S ] G[V(G)\setminus S] of G G on V ⁡ ( G ) ∖ S V(G)\setminus S is a star, where S S is the set of all leaf vertices, or if G G is a connected graph with a perfect matching consisting of pendant edges and the induced subgraph G ⁡ [ V ⁡ ( G ) ∖ S ] G[V(G)\setminus S] of G G on V ⁡ ( G ) ∖ S V(G)\setminus S is a complete graph and the weight function ω \omega satisfies ω ⁡ ( e ) = 1 \omega(e)=1 for all e ∈ E ⁡ ( G ⁡ [ V ⁡ ( G ) ∖ S ] ) e\in E(G[V(G)\setminus S]) . 1. Introduction Let G be a finite simple graph with the vertex set V(G) and the edge set E(G) . A subset X of V(G) is said to be independent if there is no edge xy\in E(G) for x,y\in X . If X is an independent set and maximal in terms of inclusion, then X is called the maximal independent set of G , and its cardinality is called the independence number of G . A graph G is called well-covered (also called unmixed ) if all maximal independent sets of G have the same independence number. It is known that a well-covered graph is a member of the class W_{2} if removing any vertex leaves a well-covered graph with the same independence number as itself (see [ 18 ] ). A graph G without isolated vertices is said to be very well-covered if |V(G)| is an even integer and every maximal independent set of G has cardinality |V(G)|/2 . A function \omega\colon E(G)\to\mathbb{Z}_{>0} is called an edge-weighted function (weighted function for short) on E(G) . The pair (G,\omega) is called a weighted graph and is denoted by G_{\omega} . If V(G)=\{x_{1},\ldots,x_{d}\} , then we can assume that R=K[x_{1},\ldots,x_{d}] is a polynomial ring over a field K . The weighted edge ideal of G_{\omega} is defined as a monomial ideal of R as follows: I(G_{\omega})=((x_{i}x_{j})^{\omega(x_{i}x_{j})}\mid x_{i}x_{j}\in E(G)). If the weighted function \omega on E(G) is the trivial one, i.e. \omega(e)=1 for all e\in E(G) , then I(G_{\omega}) is just the classical edge ideal of G , denoted by I(G) . It is known (see e.g. [ 24 , Proposition 6.1.16] ) that \ass(R/I(G))=\{(v:v\in C)\mid C\text{ is a minimal vertex cover of }G\}. In particular, \dim R/I(G)=\alpha(G) , where \alpha(G) is the maximum cardinality of independent sets in G . For an ideal I\subset R , we say that it is Cohen-Macaulay (resp. Gorenstein) if the quotient ring R/I is Cohen-Macaulay (resp. Gorenstein). A graph G is called a Cohen-Macaulay (resp. Gorenstein) graph if its edge ideal I(G) is Cohen-Macaulay (resp. Gorenstein). It is known that if G is Gorenstein, then it is Cohen-Macaulay, so it is also well-covered. Note that I(G)=\sqrt{I(G_{\omega})} , so G is Cohen-Macaulay if G_{\omega} is Cohen-Macaulay (due to [ 10 , Theorem 2.6] ). Recall that for a homogeneous ideal I\subset R and any integer n\geq 1 , the n -th symbolic power of I is defined as I^{(n)}=\bigcap\limits_{\mathfrak{p}\in\Min(I)}I^{n}R_{\mathfrak{p}}\cap R, where \Min(I) is the set of minimal primes of I . Much research has been done on the characterization of Cohen-Macaulay graphs. Examples include bipartite graphs, chordal graphs, toric graphs, large perimeter graphs, etc. ( see [ 8 , 9 , 12 , 14 , 21 , 22 , 23 ] ) . For the higher powers and higher symbolic power of I(G) , Hoang and the second author of this paper proved in [ 14 ] that I(G)^{2} is Cohen-Macaulay if and only if G is a triangle-free Gorenstein graph. Furthermore, Cowsik and Nori in [ 1 ] showed that for a homogeneous radical ideal I\subset R , I^{n} is Cohen-Macaulay for infinitely many n if and only if I is a complete intersection. In particular, I(G)^{n} is Cohen-Macaulay for infinitely many n if and only if I(G) is a complete intersection. Hoang, Minh and the second author of this paper proved in [ 13 ] that I(G)^{(2)} is Cohen-Macaulay if and only if G is a Cohen-Macaulay graph and for all edges xy , G_{xy} is Cohen-Macaulay and \alpha(G_{xy})=\alpha(G)-1 , where G_{xy}=G\setminus(N(x)\cup N(y)) is the localization of G at the edge xy . In [ 5 ] , Giancarlo, Naoki and Ken-ichi showed that I(G)^{(n)} is Cohen-Macaulay for some integer n\geq 3 if and only if G is a disjoint union of finitely many complete graphs. In this case, I(G)^{(n)} is Cohen-Macaulay for all n . We know that if I(G)^{n} is Cohen-Macaulay, then I(G)^{n}=I(G)^{(n)} . Recently, there has been a surge of interest in characterizing weight functions for which the edge ideal of a weighted graph is Cohen-Macaulay, and in computing the depth of powers of the edge ideals of some weighted graphs. For example, Paulsen and Sather-Wagstaff in [ 16 ] classified Cohen-Macaulay weighted graphs G_{\omega} where the underlying graph G is a cycle, a tree, or a complete graph. Seyed Fakhari et al. in [ 19 ] continued this study, they classified Cohen-Macaulay weighted graph G_{\omega} when G is a very well-covered graph. Recently, Diem et al. in [ 3 ] gave a complete characterization of sequentially Cohen-Macaulay weighted graphs. In [ 25 ] , Wei classified all Cohen-Macaulay weighted chordal graphs from a purely graph-theoretic point of view. Hien in [ 11 ] classified Cohen-Macaulay weighted graphs G_{\omega} if G has a girth of at least 5 . In [ 26 ] , Zhu et al. gave some exact formulas for the depth of the powers of the edge ideal of a weighted star graph and also gave some lower bounds on the depth of powers of the integrally closed weighted path. In this paper, we will focus on characterize the Cohen-Macaulayness of the second power I(G_{\omega})^{2} of the weighted edge ideal I(G_{\omega}) when the underlying graph G is a very well-covered graph. We also characterize the Cohen-Macaulayness of all ordinary powers of I(G_{\omega})^{n} when G is a tree with a perfect matching consisting of pendant edges and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a star, where S is the set of all leaf vertices, or if G is a connected graph with a perfect matching consisting of pendant edges and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a complete graph and the weight function \omega satisfies \omega(e)=1 for all e\in E(G[V(G)\setminus S]) . The article is organized as follows. In Section 2 , we will collect some of the essential definitions and terminology that will be needed later. In Section 3 , we will prove that if G is a Cohen-Macaulay very well-covered graph, then G has at least two leaves. Furthermore, if G has exactly two leaves, then it is bipartite. We also give the necessary and sufficient condition that I(G_{\omega})^{2} is Cohen-Macaulay using the weight function \omega . In Section 4 , if G is a path of length of 3 , using the weight function \omega , we give the necessary and sufficient condition that I(G_{\omega})^{n} is Cohen-Macaulay for all n\geq 1 (see Proposition 4.3 ). Under the condition that G is a tree, we give the conditions that the weight function \omega satisfies if I(G_{\omega})^{n} is Cohen-Macaulay for all n\geq 1 . Furthermore, if G is a tree with a perfect matching consisting of pendant edges and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a star, where S is the set of all leaf vertices, we show that these conditions are crucial. If G is a connected graph with a perfect matching consisting of pendant edges, and the induced subgraph G[V(G)\setminus S] of G on V(G)\setminus S is a complete graph, and the weight function \omega satisfies \omega(e)=1 for all e\in E(G[V(G)\setminus S]) , we show that I(G_{\omega})^{n} is Cohen-Macaulay for all n\geq 1 if and only if \omega(e)\geqslant 2 for any pendant edge e . 2. Preliminaries We begin this section by collecting some terminology and results from graph theory. Let G be a finite simple graph with a vertex set V(G) and an edge set E(G) . A subset C\subseteq V(G) is a vertex cover of G if, for each e\in E(G) , e\cap C\neq\emptyset . If C is minimal with respect to inclusion, then C is called a minimal vertex cover of G . Obviously, C is a vertex cover if and only if V(G)\setminus C is an independent set. If v is a vertex in G , its neighborhood is the set N_{G}(v)=\{u\in V(G)\mid vu\in E(G)\} and its degree, denoted by \deg_{G}(v) , is |N_{G}(v)| . If \deg_{G}(v)=1 , then v is called a leaf vertex. An edge that is incident with a leaf vertex is called a pendant edge. The closed neighborhood of v is N_{G}[v]=N_{G}(v)\cup\{v\} ; if there is no ambiguity on G , we use N(v) and N[v] , respectively. For an independent set S of G , we denote the closed neighborhood of S by N_{G}[S]=S\cup\{v\in V(G)\mid N_{G}(v)\cap S\neq\emptyset\} ; we write N_{G}[v_{1},\ldots,v_{s}] stands for N_{G}[S] if S=\{v_{1},\ldots,v_{s}\} . A subset M\subset E(G) is a matching if e\cap e^{\prime}=\emptyset for every pair of edges e,e^{\prime}\in M . If every vertex of G is incident with an edge in M , then M is a perfect matching of G . For a subset A\subset V(G) , let G[A] denote the induced subgraph of G on A . At the same time, we denote the induced subgraph of G on V(G)\setminus A by G\setminus A . If A=\{v\} , we will write G\setminus v instead of G\setminus\{v\} for simplicity. Let G_{\omega} be a weighted graph, its induced subgraph is a weighted graph H_{\omega} , where V(H)\subset V(G) , and for any u,v\in V(H) , uv\in E(H) if and only if uv\in E(G) , and the weight \omega_{H}(uv) of edge uv in H is equal to its weight \omega_{G}(uv) in G . A monomial ideal I is unmixed if its associated primes have the same height. It is well known that I is unmixed if R/I is Cohen-Macaulay. If I(G_{\omega}) is unmixed, we say that G_{\omega} is unmixed. Note that I(G)=\sqrt{I(G_{\omega})} , so G is well-covered if G_{\omega} is unmixed. Note also that the height I(G_{\omega}) is equal to the smallest size of the vertex covers of G . Next, we recall a formula by Hochster to ompute the depth of R/I , where I is a monomial ideal. Actually, it gives us a way to check the Cohen-Macaulayness of monomial ideals. Lemma 2.1 . [ 15 , Theorem 7.1] Let I be a monomial ideal. Then \depth R/I=\min\{\depth R/\sqrt{I\colon f}\mid f\text{ is a monomial such that }f\notin I\}. As a consequence, we obtain Lemma 2.2 . Let I be a monomial ideal. Then I is Cohen-Macaulay if and only if I has no embedded prime ideal and I\colon f is Cohen-Macaulay for every monomial f\notin I . Let V be the set of all variables of R . For a monomial f in R , its support is \supp(f)=\{x\in V\mid x\text{ is divisible by }f\} , i.e., it is the set of all variables appearing in f . For a monomial ideal I of R and a subset W of V , the restriction of I on W is I|_{W}=(f\mid f\text{ is a minimal generator of\ }I\text{ such that }\supp(f)\subseteq W), denoted by I|_{W} , and define I_{W}=IR_{W}\cap R as the localization of I with respect to W . Note that I_{W}=I\colon f^{\infty} with f=\prod_{x\in W}x . The following lemmas are obvious. Lemma 2.3 . Let I and J be two monomial ideals in R and let W be a subset of V . Then (1) (I\cap J)|_{W}=I|_{W}\cap J|_{W} ; and (2) (I^{n})|_{W}=(I|_{W})^{n} for all n\geqslant 1 . Lemma 2.4 . Let I and J be two monomial ideals in R and let W\subseteq V . Then (1) (I\cap J)_{W}=I_{W}\cap J_{W} ; (2) (I^{n})_{W}=(I_{W})^{n} for all n\geqslant 1 ; and (3) if I is Cohen-Macaulay, then I_{W} is also Cohen-Macaulay. Lemma 2.5 . Suppose that G has a pendant edge xy with \deg_{G}(y)=1 . For any integer n\geq 1 , if I(G_{\omega})^{n} is unmixed, then I((G\setminus x)_{\omega})^{n} is also unmixed. Proof. For simplicity, set I=I(G_{\omega}) and H=G\setminus x . Assume that I=Q_{1}\cap Q_{2}\cap\cdots\cap Q_{k}\cap Q_{k+1}\cap\cdots\cap Q_{m}\cap Q_{m+1}\cap\cdots\cap Q_{s} is an irredundant primary decomposition of I , where • \hgt(Q_{i})=\hgt(I) for i=1,\ldots,m ; and \hgt(Q_{i})>\hgt(I) for i=m+1,\ldots,s . • x\in Q_{i} for i=1,\ldots,k ; and y\in Q_{i} for i=k+1,\ldots,m . Since I^{n} is unmixed, we have I^{n}=I^{(n)} , where I^{(n)} is the n -th symbolic power of I . So I^{n}=Q_{1}^{n}\cap\cdots\cap Q_{k}^{n}\cap Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n} . Let I^{\prime} be the restriction of I on V(G)\setminus\{x\} , then, by Lemma 2.3 , we have I(H_{\omega})^{n}=(I^{\prime})^{n}=(I^{n})^{\prime} . So again by this lemma we get that I(H_{\omega})^{n}={Q^{\prime}}_{1}^{n}\cap\cdots\ {Q^{\prime}}_{k}^{n}\cap Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n} is a primary decomposition of I(H_{\omega})^{n} . Since every monomial generator of I(H_{\omega})^{n} contains neither x nor y , it follows that I(H_{\omega})^{n}={Q^{\prime}}_{1}^{n}\cap\cdots\cap{Q^{\prime}}_{k}^{n}. Since every {Q^{\prime}}_{i} with i=1,\ldots,k has height \hgt(I)-1 , this representation is an irredundant primary decomposition of I(H_{\omega})^{n} , and thus I(H_{\omega})^{n} is unmixed, as required. ∎ Further, we obtain Lemma 2.6 . Suppose that G has a pendant edge xy with \deg_{G}(y)=1 . For any integer n\geq 1 , if I(G_{\omega})^{n} is Cohen-Macaulay, then I((G\setminus x)_{\omega})^{n} is Cohen-Macaulay. Proof. Let I=I(G_{\omega}) , H=G\setminus x and I=Q_{1}\cap\cdots\cap Q_{k}\cap Q_{k+1}\cap\cdots\cap Q_{m}\cap Q_{m+1}\cap\cdots\cap Q_{s} be an irredundant primary decomposition of I such that • \hgt(Q_{i})=\hgt(I) for i=1,\ldots,m ; and \hgt(Q_{i})>\hgt(I) for i=m+1,\ldots,s . • x\in Q_{i} for i=1,\ldots,k ; and y\in Q_{i} for i=k+1,\ldots,m . Since I^{n} is Cohen-Macaulay, it is unmixed. Hence I^{n}=Q_{1}^{n}\cap\cdots\cap Q_{k}^{n}\cap Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n} by Lemma 2.5 . Let I^{\prime} be the restriction of I on V(G)\setminus\{x\} , then, by the proof of Lemma 2.5 , we get that I(H_{\omega})^{n}={Q^{\prime}}_{1}^{n}\cap\cdots\cap{Q^{\prime}}_{k}^{n} is an irredundant primary decomposition of I(H_{\omega})^{n} . Let P_{i}=\sqrt{Q_{i}} and P^{\prime}_{i}=\sqrt{Q^{\prime}_{i}} for i=1,\ldots,k . Let f be any monomial with \supp(f)\subseteq V(G)\setminus\{x,y\} such that f\notin I(H_{\omega})^{n} . Suppose f\notin{Q^{\prime}}_{i}^{n} for i=1,\ldots,t and f\in{Q^{\prime}}_{i}^{n} for i=t+1,\ldots,k . In particular, \sqrt{I(H_{\omega})^{n}\colon f}=\sqrt{{Q^{\prime}}_{1}^{n}\colon f}\cap\cdots\cap\sqrt{{Q^{\prime}}_{t}^{n}\colon f}={P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t}. Let g=fy^{n\omega(xy)} , then g\notin Q_{i}^{n} for i=1,\ldots,t ; and g\in Q_{i}^{n} for i=t+1,\ldots,m . It follows that I(G_{\omega})^{n}:g=(Q_{1}^{n}\colon g)\cap\cdots\cap(Q_{t}^{n}\colon g), and so \sqrt{I(G_{\omega})^{n}:g}=\sqrt{{Q}_{1}^{n}\colon g}\cap\cdots\cap\sqrt{{Q}_{t}^{n}\colon g}={P}_{1}\cap\cdots\cap{P}_{t}=(x)+{P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t}. Since I(G_{\omega})^{n}:g is Cohen-Macaulay by Lemma 2.2 , so is (x)+{P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t} . Therefore, \sqrt{I(H_{\omega})^{n}:f}={P^{\prime}}_{1}\cap\cdots\cap{P^{\prime}}_{t} is Cohen-Macaulay. It follows that I(H_{\omega})^{n} is Cohen-Macaulay again by Lemma 2.2 , as required. ∎ For a monomial u and a variable x , we denote \deg_{x}(u)=\max\{m:x^{m}|u\} . Lemma 2.7 . Suppose that I(G_{\omega})^{n} is unmixed for some n\geqslant 1 . If G has a pendant edge xy with \deg_{G}(y)=1 , then \omega(xy)\geqslant\omega(xz) for all z\in N_{G}(x) . Proof. Let I=I(G_{\omega}) and let I=Q_{1}\cap\cdots\cap Q_{k}\cap Q_{k+1}\cap\cdots\cap Q_{m}\cap Q_{m+1}\cap\cdots\cap Q_{s} be an irredundant primary decomposition of I , where \hgt(Q_{i})=\hgt(I) for i=1,\ldots,m ; and \hgt(Q_{i})>\hgt(I) for i=m+1,\ldots,s . Since I^{n} is unmixed, we have I^{n}=Q_{1}^{n}\cap\cdots\cap Q_{m}^{n}. Let P_{i}=\sqrt{Q_{i}} for i=1,\ldots,m , where x\in P_{i} for i=1,\ldots,k , and x\notin P_{i} for i=k+1,\ldots,m . Since \ass(R/I^{n})=\{P_{1},\ldots,P_{m}\} , it follows that \ass(R/I^{n})=\ass(R/I(G)) . Since xy is a pendant edge of G , every associated prime ideal of G contains either x or y , but not both. Thus, y\notin P_{i} for i=1,\ldots,k , and y\in P_{i} for i=k+1,\ldots,m . For a monomial ideal J of R , let \G(J) be the set of its minimal monomial generators. We have I^{n}=(Q_{1}^{n}\cap\cdots\cap Q_{k}^{n})\cap(Q_{k+1}^{n}\cap\cdots\cap Q_{m}^{n})=((x^{p})+J_{1})\cap((y^{q})+J_{2}) where each monomial f\in\G(J_{1}) has \deg_{x}(f)

\omega_{kt} by Eq. ( 4 ). Together with the fact that f\in J^{2} , this implies that either x_{1}^{\omega_{11}}(x_{1}y_{t})^{\omega_{1t}}\mid f or (x_{1}y_{t})^{2\omega_{1t}}\mid f . The first case is impossible because \deg_{x_{1}}(x_{1}^{\omega_{11}}(x_{1}y_{t})^{\omega_{1t}})>\deg_{x_{1}}(f) . Hence (x_{1}y_{t})^{2\omega_{1t}}\mid f . It follows that 2\omega_{1t}\leqslant\omega_{11} and 2\omega_{1t}\leqslant\omega_{kt} . Similarly, if we choose g=x_{1}^{\omega_{1k}}y_{t}^{\omega_{tt}} , then we can get 2\omega_{1t}\leqslant\omega_{tt} and 2\omega_{1t}\leqslant\omega_{1k} . The proof is now complete. ∎ Lemma 3.7 . If I(G_{\omega})^{2} is Cohen-Macaulay, then (1) 2\omega(x_{i}x_{j})\leqslant\min\{\omega(x_{i}y_{i}),\omega(x_{j}y_{j})\} if x_{i}x_{j}\in E(G) with i\neq j . (2) 2\omega(x_{i}x_{j})\leqslant\min\{\omega(x_{i}y_{k}),\omega(x_{k}x_{j})\} for all different indices i,j,k such that x_{i}y_{k} , x_{k}x_{j}\in E(G) . Proof. (1) We prove the ststement by induction on t\geqslant 2 . If t=2 , then it follows from Lemma 3.4 . Suppose t\geqslant 3 . Note that i\neq j . If G has a pendant edge x_{p}y_{p} with p\notin\{i,j\} , then I((G\setminus\{x_{p},y_{p}\})_{\omega})^{2} is Cohen-Macaulay by Lemma 2.6 . By applying the induction hypothesis on H_{\omega} , we obtain the desired inequalities. Therefore, we can assume that x_{p}y_{p} is not a pendant edge for p\notin\{i,j\} , and hence x_{i}y_{i} and x_{j}y_{j} are the only pendant edges by Lemma 3.2 . In particular, y_{i} and y_{j} are the only leaves of G . Therefore, by Lemma 3.3 , G is bipartite. Thus, by [ 8 , Theorem 3.4 ] , G has a bipartition (U,V) that satisfies the condition (*) . Furthermore, if U=\{u_{1},\ldots,u_{t}\} and V=\{v_{1},\ldots,v_{t}\} , by [ 2 , Theorem 0.2] , G has a unique perfect matching, we have \{x_{1}y_{1},\ldots,x_{t}y_{t}\}=\{u_{1}v_{1},\ldots,u_{t}v_{t}\}. Since u_{1}v_{1} and u_{t}v_{t} are pendent edges, it follows that \{x_{i}y_{i},x_{j}y_{j}\}=\{u_{1}v_{1},u_{t}v_{t}\} . We can assume that x_{i}y_{i}=u_{1}v_{1} as edges of G so that x_{j}y_{j}=u_{t}v_{t} . Since v_{1},u_{t} are leaves, we deduce that y_{i}=v_{1} and y_{j}=u_{t} . Then, the inequality now becomes 2\omega(u_{1}v_{t})\leqslant\min\{\omega(u_{1}v_{1}),\omega(u_{t}v_{t})\} , which follows from Lemma 3.6 . (2) The proof is almost the same as in the previous case. We prove by induction on t\geqslant 3 . If t=3 , since x_{k}y_{k} is not a pendent edge, we deduce that G is a bipartite graph by Lemma 3.3 . Actually, we can check that (\{x_{i},x_{k},y_{j}\},\{y_{i},y_{k},x_{j}\}) is a bipartition of G and it has a representation as in Figure 4 . With this configuration of G , the desired inequality follows from Lemma 3.6 . Figure 4. The graph G_{\omega} after swapping the endpoints of x_{j}y_{j} . Suppose that t\geqslant 4 . If G has a pendant edge x_{p}y_{p} with p\notin\{i,j\} , then I((G\setminus\{x_{p},y_{p}\})_{\omega})^{2} is Cohen-Macaulay by Lemma 2.6 . Applying the induction hypothesis to H_{\omega} , we obtain the desired inequalities. Hence we can assume that x_{p}y_{p} is not a pendant edge for p\notin\{i,j\} , and hence x_{i}y_{i} and x_{j}y_{j} are the only pendant edges of G by Lemma 3.2 . In particular, y_{i} and y_{j} are the only leaves of G . In this case, G is bipartite by Lemma 3.3 . By the same argument as in the previous case, G has a bipartition (U,V) that satisfies the condition (*) , and if U=\{u_{1},\ldots,u_{t}\} and V=\{v_{1},\ldots,v_{t}\} , then \{x_{1}y_{1},\ldots,x_{t}y_{t}\}=\{u_{1}v_{1},\ldots,u_{t}v_{t}\}. Since u_{1}v_{1} and u_{t}v_{t} are pendent edges of G , it follows that \{x_{i}y_{i},x_{j}y_{j}\}=\{u_{1}v_{1},u_{t}v_{t}\} . So either x_{i}y_{i}=u_{1}v_{1} and x_{j}y_{j}=u_{t}v_{t} or x_{i}y_{i}=u_{t}v_{t} and x_{j}y_{j}=u_{1}v_{1} . This also implies that x_{k}y_{k}=u_{s}v_{s} for some s with 1t . There exists some \ell such that \deg_{G}(y_{\ell})>1 . We can construct a new very well-covered graph G^{\prime} from G such that V(G^{\prime})=V(G) and the edge set is E(G^{\prime})=\{E(G)\setminus\{x_{i}y_{\ell}\mid x_{i}y_{\ell}\in E(G)\text{ with }i<\ell\}\}\cup\{x_{i}x_{\ell}\mid x_{i}y_{\ell}\in E(G)\text{ with }i<\ell\}. We can check that G^{\prime} satisfies the condition (*) , so it is also very well-covered. Next, we define the weight function \omega^{\prime} on E(G^{\prime}) by \omega^{\prime}(e)=\begin{cases}\omega(x_{i}y_{\ell})&\text{ if }e=x_{i}x_{\ell}\text{ and }x_{i}y_{\ell}\in E(G)\text{ with }i<\ell,\\ \omega(e)&\text{ otherwise}.\end{cases} We can check that the weight function \omega^{\prime} on E(G^{\prime}) satisfies all the conditions of our theorem and that m(G^{\prime}_{\omega^{\prime}})1 , we do the same as in the proof of Lemma 3.9 . The second step is to prove that I(G_{\omega})^{n} is Cohen-Macaulay by doing the same proof as in the proof of Theorem 3.10 , using the fact that I(G_{\omega})^{n} is unmixed, which was proved in the previous step. ∎ By virtue of Theorem 4.1 , for any \ell\geqslant 1 and any very well-covered graph G , we can construct a weight function \omega on E(G) such that I(G_{\omega})^{n} is Cohen-Macaulay for all n=1,\ldots,\ell . However, a characterization of G_{\omega} for which I(G_{\omega})^{n} is Cohen-Macaulay for a given integer n is still unknown. Our calculation supports the following conjecture. Conjecture 4.2 . Let n\geqslant 2 be an integer and let G be a very well-covered graph and \omega be a weight function on E(G) . Then I(G_{\omega})^{n} is Cohen-Macaulay if and only if I(G_{\omega})^{2} is Cohen-Macaulay and I(G_{\omega})^{n} is unmixed. In the rest of this section, we are interested in characterizing G_{\omega} such that I(G_{\omega})^{n} is Cohen-Macaulay for all n\geqslant 1 in the case where G is a tree. The structure of the graph G is given in [ 24 , Theorem 6.3.4] : G has a perfect matching \{x_{1}y_{1},\ldots,x_{t}y_{t}\} , where each y_{i} is a leaf vertex, and G[x_{1},\ldots,x_{t}] is a tree. For the case t=2 , G[x_{1},x_{2}] is only one edge, and we have the following result. Proposition 4.3 . Let G_{\omega} be a weighted tree with the edge set E(G)=\{ab,ax,by\} . Then I(G_{\omega})^{n} is Cohen-Macaulay for all n\geqslant 1 if and only if \min\{\omega(ax),\omega(by)\}\geqslant 2\omega(ab) . Proof. For simplicity, let I=I(G_{\omega}) and p=\omega(ax),k=\omega(ab),q=\omega(by) . Then the weighted graph G_{\omega} is shown as in Figure 2 and I=(a^{p}x^{p},a^{k}b^{k},b^{q}y^{q}) . If I^{n} is Cohen-Macaulay for all n\geqslant 1 , then \min\{p,q\}\geqslant 2k by Lemma 3.4 . Conversely, suppose that \min\{p,q\}\geqslant 2k . Then I has an irredundant primary decomposition I=(a^{k}b^{k},a^{p},b^{q})\cap(a^{k},y^{q})\cap(b^{k},x^{p}). For any integer n\geqslant 1 , we will prove that I^{n} is Cohen-Macaulay in the following two steps. Step 1 : We prove that I^{n}=I^{(n)} , where I^{(n)} is the n -th symbolic power of I . Let f be any monomial of I^{(n)} . Since I^{(n)}=(a^{k}b^{k},a^{p},b^{q})^{n}\cap(a^{k},y^{q})^{n}\cap(b^{k},x^{p})^{n} , we can write f=ga^{ku}b^{kv}x^{(n-v)p}y^{(n-u)q} , where g is a monomial in R and u,v\in\{0,\ldots,n\} such that ga^{ku}b^{kv}\in(a^{k}b^{k},a^{p},b^{q})^{n} . So we can write ga^{ku}b^{kv}=h(a^{k}b^{k})^{s}(a^{p})^{i}(b^{q})^{j}, where h is a monomial in R and s+i+j=n . We choose such an expression for which i+j is minimal. If i\geqslant 1 and j\geqslant 1 , then ga^{ku}b^{kv}=(ha^{p-2k}b^{q-2k})(a^{k}b^{k})^{s+2}(a^{p})^{i-1}(b^{q})^{j-1} since \min\{p,q\}\geqslant 2k . This contradicts the minimality of i+j , so either i=0 or j=0 . Without loss of generality, we can assume that j=0 . If i=0 , then s=n and ga^{ku}b^{kv}=h(a^{k}b^{k})^{n} . It follows that f=ga^{ku}b^{kv}x^{(n-v)p}y^{(n-u)q} =h(a^{k}b^{k})^{n}x^{(n-v)p}y^{(n-u)q}\in I^{n} . Suppose i>0 . Then we have b^{k}\nmid h . Because if b^{k}\mid h , we can write ga^{ku}b^{kv}=h^{\prime}(a^{k}b^{k})^{s+1}(a^{p})^{i-1} where h^{\prime}=a^{p-k}h/b^{k} , which also contradicts the minimality of i+j . So b^{k}\nmid h . Together with the equality ga^{ku}b^{kv}=h(a^{k}b^{k})^{s}(a^{p})^{i} , this forces v\leqslant s , so i=n-s\leqslant n-v . It follows that f=h(a^{k}b^{k})^{s}(a^{p})^{i}x^{(n-v)p}y^{(n-u)q}=hy^{(n-u)q}x^{(n-v-i)p}(a^{k}b^{k})^{s}(a^{p}x^{p})^{i}\in I^{n}, since i+s=n . So we always have f\in I^{n} , and hence I^{n}=I^{(n)} . Step 2 : We prove that I^{n} is Cohen-Macaulay. Suppose, on the contrary, that I^{n} is not Cohen-Macaulay. Since I^{n}=I^{(n)} , it is unmixed, so \sqrt{I^{n}\colon f} is not Cohen-Macaulay for some monomial f\notin I^{n} by Lemma 2.2 . Note that \ass(R/I^{n})=\{(a,b),(a,y),(b,x)\} . So \sqrt{I^{n}\colon f} is not Cohen-Macaulay if and only if \sqrt{I^{n}\colon f}=(a,y)\cap(b,x) . This means that f\in(a^{k}b^{k},a^{p},b^{q})^{n},f\notin(a^{k},y^{q})^{n},\text{ and }f\notin(b^{k},x^{p})^{n}. Since f\in(a^{k}b^{k},a^{p},b^{q})^{n} , we can write f=f_{1}(a^{k}b^{k})^{s}(a^{p})^{i}(b^{q})^{j} , where f_{1} is a monomial in R and s+i+j=n . Choose such an expression for which i+j is minimal. By the same argument as in the previous step, we have either i=0 or j=0 . Without loss of generality, we can assume that j=0 . It follows that f=f_{1}(a^{k}b^{k})^{s}(a^{p})^{i}=f_{1}b^{ks}a^{(p-k)i}(a^{k})^{n}\in(a^{k},y^{q})^{n} , a contradiction. So I^{n} is Cohen-Macaulay, and the proof is now complete. ∎ We now consider the case t=3 , in which case G[x_{1},x_{2},x_{3}] is just a path of length 3 . For simplicity, consider the weighted tree G_{\omega} with the edge set E(G)=\{ab,bc,ax,by,cz\} and the weight function k=\omega(ab),m=\omega(bc),p=\omega(ax),q=\omega(by),r=\omega(cz), which is shown in Figure 5 . Figure 5 . The weighted graph G_{\omega} . Lemma 4.4 . Let G_{\omega} be a weighted graph as shown in Figure 5 . If m=k , then I(G_{\omega})^{n} is not Cohen-Macaulay for all n\geqslant\max\{p,r\}/m+2 . Proof. Let I=I(G_{\omega}) , then I=((ab)^{m},(bc)^{m},(ax)^{p},(by)^{q},(cz)^{r}) . Suppose by contradiction that I(G_{\omega})^{n} is Cohen-Macaulay for some n\geqslant\max\{p,r\}/m+2 . First, we claim that \min\{p,q,r\}\geqslant 2m . Indeed, let H=G\setminus c so that I(H_{\omega})=((ab)^{m},(ax)^{p},(by)^{q}) . By Lemma 2.6 , I(H_{\omega})^{n} is Cohen-Macaulay, and hence \min\{p,q\}\geqslant 2m by Lemma 3.4 . Similarly, by considering the graph G\setminus a , we obtain r\geqslant 2m , and the claim follows. Let J=I_{\{y\}} be the localization of I with respect to the set \{y\} , then J=((ab)^{m},(bc)^{m},(ax)^{p},b^{q},(cz)^{r}) . Using the above claim, we can check that J=((ab)^{m},(bc)^{m},a^{p},b^{q},c^{r})\cap(a^{p},b^{m},z^{r})\cap(b^{m},c^{r},x^{p})\cap(b^{m},x^{p},z^{r}) is an irredundant decomposition. Since I^{n} is Cohen-Macaulay, J^{n} is also Cohen-Macaulay by Lemma 2.4 . Consequently, J^{n}=((ab)^{m},(bc)^{m},a^{p},b^{q},c^{r})^{n}\cap(a^{p},b^{m},z^{r})^{n}\cap(b^{m},c^{r},x^{p})^{n}\cap(b^{m},x^{p},z^{r})^{n}. Let f=(b^{m})^{n-1}a^{p}c^{r} , then f\in(a^{p},b^{m},z^{r})^{n}\cap(b^{m},c^{r},x^{p})^{n} and f\notin(b^{m},x^{p},z^{r})^{n} . Now we show that f\notin((ab)^{m},(bc)^{m},a^{p},b^{q},c^{r})^{n} . If this is not the case, then f could be written as f=g((ab)^{m})^{s}((bc)^{m})^{t}(a^{p})^{u}(b^{q})^{v}(c^{r})^{w}, where s,t,u,v,w\in\mathbb{N} with s+t+u+v+w=n and g is a monomial in R . Therefore, \begin{cases}p\geqslant ms+pu\\ m(n-1)\geqslant ms+mt+qv\\ r\geqslant mt+rw\end{cases} The inequality p\geqslant ms+pu forces u\leqslant 1 . Similarly, the inequality r\geqslant mt+rw forces w\leqslant 1 . So we have four possible cases: Case 1 : If u=w=0 , then s+t+v=n . Since q\geqslant 2m , we have m(n-1)\geqslant ms+mt+qv\geqslant ms+mt+2mv=m(s+t+v)+mv\geqslant mn, a contradiction. Case 2 : If u=1 and w=0 , then s+t+v=n-1 , and then m(n-1)\geqslant ms+mt+2mv=m(s+t+v)+mv\geqslant m(n-1)+mv. This implies v=0 . Since u=1 , combined with the inequality p\geqslant ms+pu , we get s=0 . Thus t=n-(s+u+v+w)=n-1 . On the other hand, since r\geqslant mt+rw and w=0 , we get n=t+1\leqslant r/m+1 . This contradicts the assumption that n\geqslant\max\{p,r\}/m+2 . Case 3 : When u=0 and w=1 . We derive a contradiction by the same argument as in the previous case. Case 4 : If u=w=1 , then, in this case, we must have s=t=0 . Hence, v=n-(s+t+u+w)=n-2 , and hence m(n-1)\geq ms+mt+qv\geqslant q(n-2)\geqslant 2m(n-2) . This forces n\leqslant 3 , a contradiction. To sum up, all cases are impossible. It follows that f\notin((ab)^{m},(bc)^{m},a^{p},b^{q},c^{r})^{n} . Hence J^{n}\colon f=((((ab)^{m},(bc)^{m},a^{p},b^{q},c^{r})^{n})\colon f)\cap((b^{m},x^{p},z^{r})^{n}\colon f) , and hence \sqrt{J^{n}\colon f}=(a,b,c)\cap(b,x,z) . In particular, \sqrt{J^{n}\colon f} is not Cohen-Macaulay, it contradicts Lemma 2.2 . Therefore, I(G_{\omega})^{n} is not Cohen-Macaulay for all n\geqslant\max\{p,r\}/m+2 , and the proof is complete. ∎ Lemma 4.5 . Let G_{\omega} be a weighted tree as shown in Figure 5 , with kk , from the second inequality of the above system, we have m(i-1)\geqslant ku+mv+qt\geqslant ku+kv+kt=k(u+v+t)=ki, and so i\geqslant m/(m-k) . On the other hand, since i=\lceil k/(m-k)\rceil , we have id_{i} , from Eq. (\ref{FY}) we have fy_{i}=h(x_{i}y_{i})^{\alpha_{i}m_{i}}\prod_{a\in V_{1}}(x_{a}y_{a})^{\alpha_{a}m_{a}}, and hence f=(\lambda x_{i}^{\alpha_{i}m_{i}-\alpha_{i}d_{i}}y_{i}^{\alpha_{i}m_{i}-1})x_{t}^{\alpha_{i}m_{i}-\alpha_{i}d_{i}}(x_{i}x_{t})^{\alpha_{i}d_{i}}\prod_{a\in V_{1}}(x_{a}y_{a})^{\alpha_{a}m_{a}}\in I^{n}, a contradiction. It follows that V_{2}\neq\emptyset . Therefore, there exists some q\in V_{2} . We consider the following two subcases: Subcase 1.1 : If d_{q}m . It follows that fy_{i}=(\lambda x_{t}^{d_{i}(t_{i}-m)}y_{i}^{m_{i}})x_{i}^{m_{i}-md_{i}}g_{1}\cdots g_{n-\beta-1}(x_{i}x_{t})^{md_{i}}, and so f=(\lambda x_{t}^{d_{i}(t_{i}-m)}y_{i}^{m_{i}-1})x_{i}^{m_{i}-md_{i}}g_{1}\cdots g_{n-\beta-1}(x_{i}x_{t})^{md_{i}}\in I^{n-\beta-1+m}\subseteq I^{n}, as \betad_{v} by the condition (1) of the lemma, it follows that f=(\lambda x_{t}^{m_{t}-d_{v}}y_{t}^{m_{t}-1})(x_{v}x_{t})^{d_{v}}(x_{t}y_{t})^{(\alpha_{t}-1)m_{t}}\prod_{a\in V_{1}}(x_{a}x_{t})^{\alpha_{a}d_{a}}\in I^{n}. In summary, we always get that f\in I^{n} in the expression \mathfrak{p}=I^{n}\colon f of the associated prime ideal \mathfrak{p} , a contradiction. The proof is now complete. ∎ We are now ready to prove Conjecture 4.8 in the case where G[x_{1},\ldots,x_{t}] is a star. Theorem 4.10 . Suppose G[x_{1},\ldots,x_{t}] is a star with the center x_{t} . Let m_{i}=\omega(x_{i}y_{i}) for i=1,\ldots,t and let d_{i}=\omega(x_{i}x_{t}) for i\neq t . Then I(G_{\omega})^{n} is Cohen-Macaulay for all n\geqslant 1 if and only if (1) m_{t}\geqslant 2\max\{d_{i}\mid i\neq t\} . (2) d_{i}\neq d_{k} for any two different x_{i}x_{t},x_{t}x_{k}\in E(G) . Furthermore, if d_{i}0 . Note that (R/J_{k-1})/(y_{k}-x_{k})\cong(R/J_{k})/(y_{k}-x_{k}) and y_{1}-x_{1},\ldots,y_{t}-x_{t} is a system of parameters for both R/J_{k-1} and R/J_{k} . This implies that (R/J_{k})/(y_{k}-x_{k}) is Cohen-Macaulay. Hence (R/J_{k-1})/(y_{k}-x_{k}) is Cohen-Macaulay. Next, we prove that y_{k}-x_{k} is regular on R/J_{k-1} . So R/J_{k-1} is Cohen-Macaulay. By Lemma 3.1 , y_{k}-x_{k} does not belong to any associated prime ideal of I(G) , so y_{k}-x_{k}\notin\bigcup_{\mathfrak{p}\in\ass(R/I(G))}\mathfrak{p}. Since \ass(R/J_{k-1})\subseteq\ass(R/I(G)) , we have y_{k}-x_{k}\notin\bigcup_{\mathfrak{p}\in\ass(R/J_{k-1})}\mathfrak{p}. Hence y_{k}-x_{k} is regular on R/J_{k-1} , and this implies that R/J_{k-1} is Cohen-Macaulay. If we choose k=0 , then J_{0} is Cohen-Macaulay, i.e. I(G_{\omega})^{n} is Cohen-Macaulay. The proof is now complete. ∎ Remark 4.11 . For the edge ideal I of a simple graph or more generalized, of a weighted oriented graph (see e.g. [ 7 ] for the definition of such a graph), if I^{n} is unmixed for all n\geqslant 1 , then the underlying graph is bipartite (see [ 6 , 20 ] ). However, this is not true for edge-weighted graphs, as in the following result. Proposition 4.12 . Let G be a connected graph with a perfect matching \{x_{1}y_{1},\ldots , x_{t}y_{t}\} with t\geqslant 2 , where each y_{i} is a leaf vertex in G . Suppose G[x_{1},\ldots,x_{t}] is a complete graph and \omega is a weight function on E(G) such that \omega(x_{j}x_{k})=1 for all x_{j}x_{k}\in E(G) . Then I(G_{\omega})^{n} is Cohen-Macaulay for all n\geqslant 1 if and only if \omega(x_{i}y_{i})\geqslant 2 for all i=1,\ldots,t . Proof. (\Longrightarrow) : For each i , we choose j\neq i . Let H=G\setminus\{x_{s}\mid s\notin\{i,j\}\} , then E(H)=\{x_{i}y_{i},x_{i}x_{j},x_{j}y_{j}\} . Since I(G_{\omega})^{n} is Cohen-Macaulay for all n\geqslant 1 , I(H_{\omega})^{n} is also Cohen-Macaulay. Thus \omega(x_{i}y_{i})\geqslant 2 by Proposition 4.3 . (\Longleftarrow) : We will prove that I(G_{\omega})^{n} is Cohen-Macaulay by induction on n . The case n\leqslant 2 is shown separately in Theorem 4.1 . So we can assume that n\geqslant 3 , and prove the statements by induction on t . The case t\leqslant 2 is shown separately in Proposition 4.3 . Thus, in the following, we can assume that t\geqslant 3 . We will divide the proof into the following two steps: Step 1 : We prove that I(G_{\omega})^{n} is unmixed. Let I=I(G_{\omega}) and m_{i}=\omega(x_{i}y_{i}) for i=1,\ldots,t . Conversely, suppose that I^{n} is not unmixed, then there exists some monomial f\notin I^{n} such that fx_{i},fy_{i}\in I^{n} for some i\in[t] . We can write fx_{i}=gf_{1}\cdots f_{n}\text{ and }fy_{i}=hg_{1}\cdots g_{n} , where g,h are monomials and f_{i},g_{i} are monomial generators of I for i=1,\ldots,n . Similarly to Claims 1 , 4 and 5 of the proof in Lemma 4.9 , we obtain that (1) \{f_{1},\ldots,f_{n}\}\cap\{g_{1},\ldots,g_{n}\}=\emptyset ; (2) there exists some p\in[n] such that g_{p}=(x_{i}y_{i})^{m_{i}} ; (3) there exists some p\in[n] such that f_{p}=x_{i}x_{j} for some j\neq i . We can assume that g_{n}=(x_{i}y_{i})^{m_{i}} and f_{n}=x_{i}x_{j} for some j\neq i . Claim : (x_{k}y_{k})^{m_{k}}\notin\{g_{1},\ldots,g_{n}\} for every k\neq i . In fact, assume that (x_{k}y_{k})^{m_{k}}\in\{g_{1},\ldots,g_{n}\} for some k\neq i . Then, we can assume that g_{n-1}=(x_{k}y_{k})^{m_{k}} , so that fy_{i}=hg_{1}\cdots g_{n-2}(x_{k}y_{k})^{m_{k}}(x_{i}y_{i})^{m_{i}}. Therefore, f=(hx_{k}^{m_{k}-2}y_{k}^{m_{k}}x_{i}^{m_{i}-2}y_{i}^{m_{i}-1})g_{1}\cdots g_{n-2}(x_{i}x_{k})^{2}\in I^{n}, a contradiction, and the claim follows. Since x_{i}x_{j}\mid fx_{i} , we have x_{j}\mid f , and hence x_{j}\mid fy_{i} . It follows that either x_{j}\mid h or x_{j}\mid g_{k} for some k\neq n . In the former case f=(h/x_{j})(x_{i}^{m_{i}-1}y_{i}^{m_{i}-1})g_{1}\cdots g_{n-1}(x_{i}x_{j})\in I^{n} , a contradiction. In the second case, by Claim, (1) and (3), we can assume that g_{k}=x_{j}x_{q} for some q\notin\{i,j\} . Without loss of generality, we can assume that k=n-1 . Then f=(hx_{i}^{m_{i}-2}y_{i}^{m_{i}-1})g_{1}\cdots g_{n-2}(x_{i}x_{j})(x_{i}x_{q})\in I^{n}, a contradiction. This implies that I^{n} is unmixed. Step 2 : We prove that I(G_{\omega})^{n} is Cohen-Macaulay. This can be shown by similar arguments as in the proof of Theorem 4.10 , so we omit its proof. ∎ Data availability The data that has been used is confidential.