On Gorenstein Circulant Graphs and Gorenstein SQC Graphs
Ashkan Nikseresht Mohammad Reza Oboudi







On Gorenstein Circulant Graphs and Gorenstein  Graphs
    Ashkan Nikseresht and Mohammad Reza Oboudi

Department of Mathematics, Shiraz University,

71457-13565, Shiraz, Iran

E-mail: ashkan_nikseresht@yahoo.com

E-mail: mr_oboudi@yahoo.com 
    
===========================================================================================================================================================================================





We characterize some graphs with a Gorenstein edge ideal. In particular, we show that if G is a circulant graph
with vertex degree at most four or a circulant graph of the form C_n(1,…, d) for some d≤ n/2, then G is
Gorenstein if and only if G≅ tK_2, G≅ tC̱_̱ṉ or G≅ tC_13(1,5) for some integers t and n≥
4. Also we prove that if G is a  graph, then G is Gorenstein if and only if each component of G is either
an edge or a 5-cycle.


Keywords:  Gorenstein simplicial complex; Edge ideal; Circulant graph;  graph.

2010 Mathematical Subject Classification: 13F55, 13H10, 05E40.


                                        

§ INTRODUCTION



Throughout this paper, K is a field, S=K[x_1,…, x_n] and G denotes a simple undirected graph with vertex set
(G)={v_1,…, v_n} and edge set (G). Recall that the edge ideal I(G) of G is the ideal of S
generated by {x_ix_j|v_iv_j∈(G)}. Many researchers have studied how algebraic properties of S/I(G) relates
to the combinatorial properties of G (see <cit.> and references therein). One of the
algebraic properties that recently has gained attention is the property of being Gorenstein. We say that G is a
Gorenstein (resp, Cohen-Macaulay or CM for short) graph over K, if S/I(G) is a Gorenstein (resp. CM) ring. When G
is Gorenstein (resp. CM) over every field, we say that G is Gorenstein (resp. CM). In <cit.> and
<cit.> a characterization of planar Gorenstein graphs of girth ≥ 4 and triangle-free Gorenstein graphs,
respectively, is presented. Also in <cit.> a condition on a planar graph equivalent to being Gorenstein is
stated.

In this paper, first we recall some needed concepts and preliminary results. Then in Section 3, we characterize some
graphs with a Gorenstein edge ideal. In particular, we show that if G is a circulant graph with vertex degree at most
four or a circulant graph of the form C_n(1,…, d) for some d≤ n/2, then G is Gorenstein if and only if
G≅ tK_2, G≅ tC̱_̱ṉ or G≅ tC_13(1,5) for some integers t and n≥ 4. Also we prove that if
G is a  graph, then G is Gorenstein if and only if each component of G is either an edge or a 5-cycle.


                                        

§ PRELIMINARIES



Recall that a simplicial complex Δ on the vertex set V={v_1,…, v_n} is a family of subsets of
V (called faces) with the property that {v_i}∈Δ for each i∈ [n]={1,…,n} and if A
B∈Δ, then A∈Δ. In the sequel, Δ always denotes a simplicial complex. Thus the family
Δ(G) of all cliques of a graph G is a simplicial complex called the clique complex of G. Also
Δ(G̱) is called the independence complex of G, where G̱ denotes the complement of G. Note that
the elements of Δ(G̱) are independent sets of G. The ideal of S generated by {∏_v_i∈ F x_i|F
V is a non-face of Δ} is called the Stanley-Reisner ideal of Δ and is denoted by I_Δ and
S/I_Δ is called the Stanley-Reisner algebra of Δ over K. Therefore we have I_Δ(G̱)=
I(G). Many researchers have studied the relation between combinatorial properties of Δ and algebraic properties
of S/I_Δ, see for example <cit.> and their references.

By the dimension of a face F of Δ, we mean |F|-1 and the dimension of Δ is defined as
max{(F)|F∈Δ}. Denote by α(G) the independence number of G, that is, the maximum size
of an independent set of G. Note that α(G)=Δ(G̱)+1. A graph G is called well-covered, if
all maximal independent sets of G have size α(G) and it is said to be a W_2 graph, if |(G)|≥ 2
and every pair of disjoint independent sets of G are contained in two disjoint maximum independent sets. In some
texts, W_2 graphs are called 1-well-covered graphs. In the following lemma, we have collected some known results on
W_2 graphs and their relation to Gorenstein graphs.



  *  (<cit.> or <cit.>)If G is a graph without
    isolated vertices and G is Gorenstein over some field K, then G is a W_2 graph.


  *  (<cit.>) If G is triangle-free (that is, no subgraph of G
    is a triangle) and without isolated vertices, then G is Gorenstein G is W_2.





  *  (<cit.>) The degree of every vertex of a connected non-complete W_2 graph is at
    least 2.



Recall that if F∈Δ, then _Δ(F)={A F| F A∈Δ}. Suppose that F(G). By
[F] we mean F∪{v∈(G)| uv∈(G) for some u∈ F} and we set G_F=G[F]. Thus if F is
independent, then _Δ(G̱) F= Δ(G̱_̱F̱). Also the polynomial I(G,x)=∑_i=0^α(G)
a_ix^i, where a_i is the number of independent sets of size i in G, is called the independence polynomial
of G. It should be mentioned that, if we set f_i=a_i+1 for -1≤ i<α(G), then the vector (f_-1,
f_0,…, f_α(G)-1) is called the f-vector of Δ(G̱) in the literature of combinatorial commutative
algebra.

Theorem 5.1 of <cit.> states conditions on Δ equivalent to the statement “Δ is Goresnstein over
K”. Applying this theorem to the independence complex of G, we deduce the following characterization of Gorenstein
graphs. The details of the proof can be found in <cit.>.

Suppose that G is a graph without isolated vertices. Then G is Gorenstein over K G is CM over K,
I(G,-1)= (-1)^α(G) and G̱_̱F̱ is a cycle of length at least 4 for each independent set F of G with
size α(G)-2. In particular, if α(G)=2, then G is Gorenstein G is the complement of a cycle.

















The above results can be applied to see that there are few Gorenstein graphs in many well-known classes of graphs. For
example, let G=K_n (the complete graph on n vertices) for n≥ 2. Then I(G,x)=1+nx and α(G)=-1. Thus by
goren graphs, G is Gorenstein n=2. Therefore, the only Gorenstein complete graphs are K_2 and K_1.
Also it follows from <cit.> and <cit.> that every CM bipartite graph and every CM very
well-covered graph (that is, a well-covered graph G with |(G)|= 2α(G)) has a vertex of degree 1, hence by
W2, we see that the only connected Gorenstein bipartite or very well-covered graphs are K_2 and K_1. Also if
G is  an n-cycle for n≥ 3, then G is W_2 only if n=3 or n=5 and it follows from goren graphs,
that the only Gorenstein cycle is C_5. In the next section, we search for Gorenstein graphs in two other classes of
graphs, namely,  graphs and circulant graphs.


                    

§ GORENSTEIN CIRCULANT AND  GRAPHS


In this section, we recall the definition of circulant and  graphs and characterize Gorenstein  graphs and
Gorenstein circulant graphs with certain conditions. First, we consider circulant graphs. Suppose that n≥ 3 and
S{1,…,n/2}. Then the circulant graph C_n(S) is the graph with vertex set [n] such that
i,j is an edge of C_n(S) if and only if min{|i-j|, n-|i-j|}∈ S. In other words, assuming that i>j, the
vertices i and j are adjacent i-j∈ S∪ (n-S), where by n-S we mean {n-s|s∈ S}. In
<cit.>, well-covered circulant graphs are studied and in <cit.>, CM circulant graphs with degree
3 and CM circulant graphs of the form C_n(1,…, d) are characterized. Here we characterize Gorenstein circulant
graphs with degree ≤ 4 and Gorenstein circulant graphs of the form C_n(1,…, d).


Assume that n≥ 3, d≤n/2 and K is an arbitrary field and let G=C_n(1,…, d). Then G is
Gorenstein (over K) n=2d+3.


If α(G)=1, then G is a complete graph. But no complete graph on more than two vertices is Gorenstein. So
α(G)≥ 2. Note that each vertex of G is adjacent exactly to the (cyclically) next and  previous d
vertices. Thus the set A_t={1,d+2,2d+3, …, 1+t(d+1)} is an independent set of G, if 1+t(d+1)≤ n-d and
is a maximal independent set if t=t_0=(n-d-1)/(d+1). Since G is well-covered, t_0=α(G). Assume that
α(G)≥ 3. Set x=1+t_0(d+1) and F=A_t_0{1,x}. Then by goren graphs G̱_̱F̱ is a cycle, that
is each vertex of G_F is adjacent to all except two other vertices of G_F. Note that G_F is the induced subgraph
of G on vertices x,x+1, …, n, 1. Since the vertices of G_F which are not adjacent to 1 are x, x+1, …,
n-d, we conclude that n-d=x+1 (see fig-Cn). But then x+1 is adjacent to all vertices of G_F, except 1
which is a contradiction. Consequently, α(G)=2 and by goren graphs, G̅ is a cycle. Thus degree of
each vertex of G which is 2d must equal n-3, that is, n=2d+3 as required. Conversely, if n=2d+3, then G is
the complement of cycle and hence Gorenstein.




Now we are going to characterize Gorenstein circulant graphs with vertex degree ≤ 4. Note that  the only circulant
graphs with degree 1 are C_2n(n) which are disjoint unions of a set of edges and hence are Gorenstein. Also
connected circulant graphs with vertex degree 2 are exactly the cycles C_n which are Gorenstein n=5. In
<cit.>, CM graphs with vertex degree 3 are characterized. Using their results we get the following. Note
that Gorenstein graphs with vertex degree 3 are C_2n(a,n) for some 1≤ a<n.


The circulant graph G=C_2n(a,n) with 1≤ a<n is Gorenstein 2n/(a,2n)=3. In this case, G is
isomorphic to a disjoint copies of complement of a 6-cycle.


Let t=(a,2n) and assume that G is Gorenstein. Since G is CM and according to <cit.>, we get that 2n/t=3 or 2n/t=4. If 2n/t=4, then by <cit.>, G is isomorphic
to t copies of C_4(1,2)=K_4 which is not Gorenstein. So 2n/t=3. Conversely, if 2n/t=3, then by <cit.>, G is isomorphic to t/2 copies of C_6(2,3)=C̱_̱6̱ which is Gorenstein according to
goren graphs.






It remains to characterize circulant graphs with vertex degree equal to 4. These graphs are C_n(a,b) with 1≤
a<b<n/2. For this, we need several lemmas. In the sequel, we always assume that 1≤ a<b<n/2. It should be
mentioned that in what follows we have checked that some specific graphs are Gorenstein or W_2 or …, using the
computer algebra system Macaulay 2 <cit.>.


Suppose that B is an independent set of G and v∈ B. If B∩_G(x)≠{v} for each x∈_G(v), then
G is not W_2.


Suppose that G is W_2. By replacing B with a maximum independent set of G containing B, we can assume that
B is an independent set of size α(G). Let A_1={v} and A_2=B{v}. Since G is W_2, there are
disjoint maximum independent sets B_1 and B_2 containing A_1 and A_2, respectively. Assume that
B_2=A_2∪{x}. As x∉ B_1, we have x≠ v. If x is not adjacent to v, then since B is a maximum
independent set of G, x is adjacent to some vertex of B{v}=A_2 B_2, which contradicts independency of
B_2. Thus x is adjacent to v. Hence by assumption, there is a vertex y∈ B∩_G(x), with y≠ v. Again
y∈ A_2 B_2 and we get a contradiction. Consequently, G is not W_2.


Suppose that G=C_n(a,b) and d|n d|a and d|b. Then G is isomorphic to d disjoint copies of
C_n/d(a/d,b/d).


For each 0≤ i<d, let V_i={v∈(G)| v≡ i d}. Note that for each such i, we have
|(kd+i)-(k'd+i)| ∈{a,b} |(k-k')|∈{a/d,b/d}. Thus the induced subgraph of G on each V_i is
isomorphic to C_n/d(a/d,b/d) and it is clear that there is no edge in G between V_i and V_j for i≠ j and
the result follows.


Note that when (n,a)=1, then a has a multiplicative inverse modulo n, which we denote by a^-1.

If (n,a)=1 (resp. (n,b)=1), then C_n(a,b) is isomorphic to C_n(1,d) with d=min{a^-1b n,
-a^-1b n} (resp. d=min{b^-1a n, -b^-1a n}).


Assume that (n,a)=1 (the proof for (n,b)=1 is similar). So a has an inverse modulo n and d is
well-defined and the “min” in the definition of d guarantees d< n/2 . For each i∈(C_n(1,d)) set
ϕ(i)=1+(i-1)a n and consider ϕ as a map C_n(1,d)→ C_n(a,b). If for 1≤ i,i'≤ n we have
ϕ(i)=ϕ(i'), then i≡ i' n (because a is invertible modulo n) and hence i=i'. Thus ϕ is
one-to-one and onto. Also it is easy to verify that ϕ(i) and ϕ(i+1) and also ϕ(i) and ϕ(i+d)are
adjacent in C_n(a,b) (where we compute i+1 or i+d modulo n, if i+1>n or i+d>n, respectively). Since the two
graphs have the same number of edges, it follows that ϕ is an isomorphism.



For n≥ 4, the graph G=C_n(1,2) is W_2 n∈{4,5,7,8}.


Suppose that G is W_2 and hence well-covered. By <cit.> we have n≤  8 or n=11. One
can check that for n=6 or 11, G is not W_2 and for the other possible n's, G is W_2.


Now we can characterize Gorenstein and W_2 circulant graphs of degree 4.

Suppose that 1≤ a <b <n/2. The graph C_n(a,b) is Gorenstein (over K) (n,a,b)∈ where

    = {   (7d,d,2d), (7d,d,3d), (7d,2d,3d), (13d,d,5d), 
        (13d,2d,3d),(13d,4d,6d)|d∈}.

Also C_n(a,b) is W_2 
    (n,a,b)∈∪{(5d,d,2d), (8d, d,2d), (8d, 2d, 3d)|d∈}.



Assume that G is W_2. By using gcd n,a,b=1, we assume that (n,a,b)=1 (which corresponds to d=1).
First we prove the following claim.



  
Claim. One of the following relations hold: n=2a+b or n=a+2b or n=2a+3b or n=3a+2b or
2n=2a+3b or 2n=3a+2b.



    Proof of Claim.
 Let B={1,1+a+b,n-a- b+1}. Note that vertices 1+a and 1+b are adjacent to
1+a+b and vertices n-a+1 and n-b+1 are adjacent to n-a-b+1, thus every neighbor of 1 has a neighbor in
B{1}. If B is independent, then by W2lem with v=1, we deduce that G is not W_2. Therefore B is
not independent. Suppose that 1+a+b∈(1). Then as 1+a+b>1, we should have either a+b∈{a,b} (which is not
possible) or a+b∈{n-a,n-b}. The latter condition is equivalent to either n=2a+b or n=a+2b. Similarly if
n-a-b+1∈(1), then again either n=2a+b or n=a+2b.

Now assume that 1+a+b∈(n-a-b+1). If 1+a+b<n-a-b+1, then n-2a-2b∈{a,b,n-a,n-b} which implies that either
n=2a+3b or n=3a+2b. Finally if n-a-b+1<1+a+b, then we must have 2a+2b-n∈{a,b,n-a,n-b}, that is, either
n=a+2b or n=2a+b or 2n=3a+2b or 2n=2a+3b. This concludes the proof of the claim. Now we consider several cases.



  
Case 1: n=2a+b or n=a+2b. Assume that n=a+2b and let d=(n,b). Then d|a and hence
d=(n,a,b)=1. Note that a≡ 2b n and hence b^-1a ≡ 2 n. Thus according to gcd
n,a=1, G is isomorphic to C_n(1,2). Also if n=2a+b, a similar argument shows that G≅ C_n(1,2). Note that
since degree of each vertex in G is 4, n≥ 5. Therefore, it follows from W2Cn1,2, that n∈{5,7,8}.
Consequently, in this case G is W_2 (n,a,b) equals one of the following: (5,1,2), (7,1,3), (7,2,3) or
(8,2,3). Moreover, according to Cn(1..d), in this case G is Gorenstein n=7.



  
Case 2: n=2a+3b. Consider B={1,1+2a, 1+b-a, n-a-b+1}. Every neighbor of 1 has a neighbor
in B{1}. Hence by W2lem, B is not independent. If 1+2a ∈(1), then 2a∈{a,b,n-a,n-b}. The
only possible case is that 2a=b (for example, if 2a=n-a, then by replacing n with 2a+3b, it follows that
a=3b, which contradicts a<b). But then n=8a and hence a=(n,a,b)=1, that is, (n,a,b)=(8,1,2). Note that
C_8(1,2) is W_2 but not Gorenstein, according to Cn(1..d) and W2Cn1,2. If 1+b-a∈(1), then
again the only possible case is b-a=a which leads to (n,a,b)=(8,1,2) as above. Also note that if n-a-b+1∈(1), then by the proof of the claim above, n=2a+b or n=a+2b which contradicts the assumption of this case.

Now assume 1+2a and 1+b-a are adjacent. If 1+b-a> 1+2a, then we have b-3a∈{a,b,n-a,n-b}. But the only
possible case is b-3a=a, or equivalently b=4a. Similar to the case b=2a, we see that a=(n,a,b)=1 and
(n,a,b)=(14,1,4). But C_14(1,4) is not W_2. If 1+b-a<1+2a, then we have 3a-b∈{a,b,n-a,n-b}. It follows
that either b=2a or 2b=3a. The former case was dealt above. In the latter case, we have b=3t for some integer t
and a=2t, hence n=13t and t=(n,a,b)=1, that is, (n,a,b)=(13,2,3). Using Macaulay 2, we see that
C_13(2,3) is W_2. Also no two neighbors of 1 in C_13(2,3) are adjacent, which means, 1 is not in any triangle
of C_13(2,3). But circulant graphs are vertex transitive and hence C_13(2,3) is triangle-free and Gorenstein by
W2tri-free Goren.

Finally, noting that max{1+2a, 1+b-a}< n-b-a+1= a+2b+1, we see that {1+2a,1+b-a}∩(n-b-a+1)≠
2a+b or 2b-a are in {a,b,n-a,n-b}. But all of these cases lead to contradictions with 1≤ a<b<n/2 and
are not possible. Consequently, under the assumption of case 2, G is W_2 (n,a,b) is (8,1,2) or (13,2,3)
and only in the latter case G is Gorenstein.



  
Case 3: n=3a+2b. Consider B={1, 1+b-a, 1+b+a, n-b+a+1}. By W2lem, B is not
independent. Note that v_1=1< v_2=1+b-a< v_3=1+b+a<v_4=n-b+a+1=1+4a+b. Thus there are some i and j such that
1≤ i<j≤ 4 and  v_j-v_i∈{a,b,n-a,n-b}. Writing down all of these equations for 1≤ i<j≤ 4 and
ruling out those which contradict 1≤ a<b<n/2, we deduce that either b=2a or b=3a or b=5a or 2b=3a. Similar
to the above argument, in the first three cases, it follows that a=(n,a,b)=1 and in the last case
a/2=b/3=(n,a,b)=1. Therefore, (n,a,b) is one of the following: (7,1,2) or (9,1,3) or (13,1,5) or
(12,2,3). Using Macaulay 2, we see that G is W_2 only in the cases (n,a,b)∈{(7,1,2), (13,1,5)}. Also
C_7(1,2) is Gorenstein by Cn(1..d) and C_13(1,5) is Gorenstein, because it is triangle-free and W_2.



  
Case 4: 2n=2a+3b. First note that in this case b is even and we have b<2a (else
n≤ 3b/2+b/2= 2b, contradicting b<n/2). Let B={1, 1+b-a, n-b-a+1=1+b/2, 1+2a}. By W2lem, B is not
independent and hence the difference of two of the elements of B should be in {a,b,n-b,n-a}. The equations that
can be derived from this point and not contradicting 1≤ a<b<min{n/2,2a} are: 3a=2b, 4a=3b or 6a=5b.
Assume that 3a=2b, then a=2t and b=3t. Since b is even, t=2t' and hence n=a+3b/2=13t'. Since
t'=(n,a,b)=1, we deduce that (n,a,b)=(13,4,6). By a similar argument in other cases we have (n,a,b)=(9,3,4)
or (14,5,6). Neither C_14(5,6) nor C_9(3,4) is W_2. Consequently, G is W_2 (n,a,b)=(13,4,6) and
if this is the case, then G is also Gorenstein, because C_13(4,6) is triangle-free.



  
Case 5: 2n=3a+2b. In this case, a is even and b<3a/2. Let B={1< 1+b-a< 1+n-b-a= 1+a/2<
1+5a/2}. Note that (1+5a/2)-(1+a)=n-b and hence 1+a is adjacent to 1+5a/2. Similarly, each other neighbor of
1 is adjacent to an element of B{1}. If B is not independent, then the difference of two of its members
should be in {a,b,n-a,n-b}. But all of the equations that follow from this, contradict 1≤
a<b<min{3a/2,n/2}. Hence B is independent and by W2lem, G is not W_2, that is, this case is not
possible. This completes the proof of the theorem.


We can simplify the above theorem, noting that several of the graphs in that theorem are isomorphic.

Let G be a circulant graph with vertex degree 4. Then G is W_2 G is isomorphic to disjoint copies of
one of the following graphs: C_7(1,2), C_13(1,5), C_5(1,2), C_8(1,2). Moreover, G is Gorenstein it is
isomorphic to a disjoint copies of C_7(1,2) or to a disjoint copies of C_13(1,5).


Note that using gcd n,a=1, we get C_13(2,3)≅ C_13(4,6)≅ C_13(1,5), C_7(1,2)≅ C_7(2,3)≅
C_7(1,3) and C_8(2,3)≅ C_8(1,2). Now the result follows from circulant 4 main and gcd n,a,b=1.


Suppose that H is a graph and t∈. By tH we mean the graph consisting of t disjoint copies of H.
Summarizing our results on Gorenstein circulant graphs, we get the following.

Suppose that G is a circulant graph with vertex degree ≤ 4 or a circulant graph of the form C_n(1,…, d)
for some d≤ n/2. Then G is Gorenstein G≅ tK_2, G≅ tC̱_̱ṉ or G≅ tC_13(1,5) for some
t∈ and 4≤ n∈.






Next we consider  graphs. Our interest in  graphs arise form the fact that these graphs are CM and also every
CM graph with girth at least 5 or every CM graphs which does not contain any cycles of length 4 or 5 is in the class
, see <cit.>. We recall the definition of  graphs from <cit.>. By a simplicial
vertex of G, we mean a vertex v such that _G[v] is complete and in this case we call _G[v] a simplex
of G. Furthermore, a 5-cycle C of G is called a basic 5-cycle when C does not contain two adjacent
vertices both with degree more than 2. Also a 4-cycle C is said to be basic, if it contains two adjacent
vertices of degree 2 and the two other vertices of C each belong to a simplex or to a basic 5-cycle. For a basic
4-cycle C we denote the set of degree 2 vertices of C by (C) and call them basic vertices of C. If
there are simplices S_1, …, S_m, basic 5-cycles C_1, …, C_t and basic 4-cycles Q_1, …, Q_r of G
such that

    (G)=⋃_i=1^m S_i ∪⋃_i=1^t (C_j) ∪⋃_i=1^r (Q_i)    *

is a partition of (G), we say that G is in the class  (or simply, G is ) and call eq1 a
 partition of (G). Note that in this case, G is well-covered and has independence number equal to
m+2t+r (see <cit.>).


Suppose that G has no isolated vertex and is in the class . Then G is Gorenstein each component of G is
either an edge or a 5-cycle.


Since G is Gorenstein all of its components are so, we assume that G is connected. Suppose that eq1 is
a  partition of (G). First note that r=0, since by <cit.> every vertex of a 4-cycle of
G has degree at least 4 and G cannot have any basic 4-cycles. Suppose that S_i=[x_i]. If (x_i)=1 for some
i, then it follows from W2 that G is just an edge. Thus assume that (x_i)≥ 2 for each i.

Suppose that m>1. Note that in each basic 5-cycle of an arbitrary graph, there exist at least two non-adjacent
vertices of degree two. Let F be the independent set consisting of x_3,…,x_m and two non-adjacent vertices of
degree two from each C_i. Then |F|=α(G)-2 and by goren graphs G̱_̱F̱ is a cycle. But as x_1 is not
adjacent to N_G[x_2] in G and N_G[x_2](G_F), we see that _G̱_̱F̱(x_1)≥ |_G[x_2]|≥ 3, which
is a contradiction. If m=1, then t>0, else G is a complete graph on at least 3 vertices and is not Gorenstein.
Let F be the independent set consisting of one degree 2 vertex of C_1, say y, and two non-adjacent vertices of
degree 2 from each C_j with j>1. Again G̱_̱F̱ should be a cycle but deg_G̱_̱F̱(y)≥ |_G[x_1]|≥ 3.
Therefore, we conclude that m=0.

Now suppose that t≥ 2. Because G is connected, there is an edge between two vertices of two of the C_i's, say
vertices y_1 and y_2 of C_1 and C_2, respectively. At least one of the vertices of C_1 which are not adjacent
to y_1 has degree 2, because C_1 is basic; call this vertex y'_1. Let F to be the independent set containing
y'_1,y_2 and two non-adjacent vertices of degree 2 from each of the C_i for i>2. Then G_F is the disjoint union
of an edge and an isolated vertex which is not the complement of a cycle. This contradicts goren graphs and we
conclude that t=1. Consequently, either G= C_1 is a 5-cycle, or G is obtained from C_1 by adding one edge. In
the latter case, by applying goren graphs, we see that G is not Gorenstein and the result follows.







                                             99


bal ver dec J. Biermann and A. Van Tuyl, Balanced vertex decomposable simplicial complexes and their
    h-vectors, Elec. J. Combin. 20(3), #P15, 2013.




circulant J. Brown and R. Hoshino, Well-covered circulant graphs, Disc. Math. 311, 144–251,
    2011.

CM ring W. Bruns and Jürgen Herzog, Cohen-Macaulay Rings, Cambridge University Press,
    Cambridge, 1993.





very well M. Crupi, G. Rinaldo and N. Terai, Cohen-Macaulay edge ideals whose height is half of the
    number of vertices, Nagoya Math. J. 201, 116–130, 2011.









M2 D. R. Grayson  and M. F. Stillman, Macaulay2, a software system for research in algebraic
    geometry, Available at <http://www.math.uiuc.edu/Macaulay2/>.

hibi J. Herzog  and T. Hibi, Monomial Ideals, Springer-Verlag, London , 2011.

large girth D. T. Hoang, N. C. Minh and T. N. Trung, Cohen-Macaulay graphs with large girth, J.
    Algebra
    Appl.
    14:7,
    paper No. 1550112, 2015.

tri-freeD. T. Hoang and T. N. Trung, A characterization of triangle-free Gorenstein graphs and
    Cohen-Macaulayness of second powers of edge ideals, J. Algebr. Combin. 43, 325–338, 2016.




my vdec A. Nikseresht, Chordality of clutters with vertex decomposable dual and ascent of clutters,
    J. Combin. Theory —Ser. A, accepted for publication,  arXiv: 1708.07372.

our chordal A. Nikseresht and R. Zaare-Nahandi, On generalization of cycles and chordality to clutters from
    an algebraic viewpoint, Algebra Colloq. 24:4, 611–624,  2017.

alpha=3 M. R. Oboudi and A. Nikseresht, On Gorenstein graphs with independence number three, preprint.

pinter1 M. R. Pinter, A class of planar well-covered graphs with girth four, J. Graph Theory
    19:1, 69–81, 1995.




block cactus B. Randerath and L. Volkmann, A characterization of well covered block-cactus graphs,
    Australas. J. Combin. 9, 307–314, 1994.

stanley R. P. Stanley, Combinatorics and Commutative Algebra, Birkhäuser, Boston, 1996.






W2 J. W. Staples, On some subclasses of well-covered graphs, J. Graph Theory 3,
    197–204, 1979.

planar goren T. N. Trung, A characterization of Gorenstein planar graphs, in T. Hibi, ed., Adv. Stud.
    Pure Math., Vol. 77: The 50th Anniversary of Gröbner Bases, 399–409, 2018, arXiv:1603.00326v2.

CM circulant K. N. Vander Meulen, A. Van Tuyl and C. Watt, Cohen-Macaulay circulant graphs, Comm.
    Algebra
    42,
    1896–1910,
    2014.



