On Betti numbers of edge ideals of crown graphs

Abstract

An n-crown $\mathcal {C}_{n,n}$ on 2n vertices is a graph obtained from complete bipartite graph ${K}_{n,n}$ by removing edges of a perfect matching. Given a finite simple graph G, one can associate a simplicial complex $\Delta (G)$. In this paper, we use combinatorial data from the associated simplicial complex $\Delta (\mathcal {C}_{n,n})$ of the crown graph $\mathcal {C}_{n,n}$ and give a formula to find Betti numbers of the form $\beta _{i,i+1}$ of edge ideals of $\mathcal {C}_{n,n}$. We also present a formula to find a particular Betti of the edge ideal of a crown graph. We explicitly compute the projective dimension of the edge ideals of crown graphs using domination parameters of the graphs.

1 Introduction

Throughout this paper $\Bbbk$ will denote a field. Let $G=(V,E)$ be a finite simple (no loops or multiple edges) undirected graph with vertex set $V(G)=\{x_1, x_2, \ldots , x_n\}$ and edge set E(G). We can associate to G a quadratic square-free monomial ideal $I(G)=(x_ix_j {\mid } \{x_i,x_j\}\in E(G)$ in the polynomial ring $R=\Bbbk [x_1,x_2,\ldots ,x_n]$, where the vertex $x_i$ is identified with the variable $x_i$. The ideal I(G) is called the edge ideal of G and was first introduced by Villarreal (1995). We study edge ideals mainly to investigate relations between algebraic properties of edge ideals and combinatorial properties of graphs; see Hà and Van Tuyl (2007), Morey and Villarreal (2012), Villarreal (1995) and their references. We mainly focus on describing invariants of I(G) in terms of G.

For any edge ideal I(G) in $R=\Bbbk [x_1,x_2,\ldots ,x_n]$ there exists an $\mathbb {N}$-graded minimal free resolution

$$\begin{aligned} 0\rightarrow \bigoplus _{j=1}^{s_p}R(-j)^{\beta _{p,j}}\rightarrow \cdots \rightarrow \bigoplus _{j=1}^{s_1}R(-j)^{\beta _{1,j}}\rightarrow R \rightarrow R/I(G)\rightarrow 0. \end{aligned}$$

of R / I(G) over R, in which $R(-j)$ represents the graded free module obtained by shifting the degrees of elements of R by j. The number $\beta _{i,j}$ is called ith graded Betti number of R / I(G) in degree j and we write $\beta _{i,j}(G)$ for $\beta _{i,j}(R/I(G))$. The length p of the resolution is called projective dimension of R / I(G) and is denoted by pd(R / I(G)) (for the sake of brevity, we write pd$(G)=\text {pd}(R/I(G))$), that is,

$$\begin{aligned} \text {pd}(G)=\text {max}\{i~|~\beta _{i,j}(G)\ne 0~ \text {for some }j\}. \end{aligned}$$

Also, the Castelnuovo–Mumford regularity or simply regularity of R / I(G) is denoted by reg(R / I(G)) (we write reg(G) = reg(R / I(G))) is defined by

$$\begin{aligned} \text {reg}(G)=\text {max}\{j-i~|~\beta _{i,j}(G)\ne 0\}. \end{aligned}$$

Many authors have investigated these invariants, e.g., (Barile 2005; Hà and Van Tuyl 2008; Jacques 2004; Jacques and Katzman 2005; Katzman 2006; Kummini 2009; Mahmoudi et al. 2011; Zheng 2004). The projective dimension and regularity of a forest, which is a graph with no cycles, was first characterized by Zheng (2004). Later Hà and Van Tuyl (2008)  extended this characterization of regularity to that for chordal graphs. Katzman (2006)  proved some results on non-vanishingness of the graded Betti numbers. For other results and problems in this area we refer to  Hà and Van Tuyl (2007). The regularity of a certain class of edge ideals was characterized in Francisco et al. (2009), Hà and Van Tuyl (2008), Khosh-Ahang and Moradi (2014), Kummini (2009), Mahmoudi et al. (2011), Woodroofe (2014) and Zheng (2004) with a notion of the three-disjointness of edges which we are going to discuss in Sect. 2. In this paper, we give a formula (Theorem 3.1) to find the Betti numbers of the form $\beta _{i,i+1}$ of edge ideals of a crown graph. We also prove a result (Theorem 3.9) to find a particular Betti number of a crown graph. In addition to this, we compute the projective dimension of the edge ideals of crown graphs.

Now we describe the organization of the paper. In Sect. 2 we recall some definitions and introduce the notion of the strongly disjoint set of bouquets. Moreover, in this section, we recall some well-known results by Hochster (1975) and Katzman (2006). In Sect. 3 we introduce the crown graphs and prove some results . In particular, we prove Theorems 3.1 and 3.9. In Sect. 4 we discuss domination parameters of graphs and present a result on projective dimension of edge ideals of crown graphs.

2 Preliminaries

In this section, we prepare some definitions on graphs and recall some known results about the Betti numbers and the regularity of edge ideals. We also fix some notations that are used in subsequent sections.

2.1 Simplicial complexes and Hochster’s formula

Definition 1

Let $[n]= \{1, 2, \ldots , n\}$. A $simplicial \ complex \ \Delta$ on [n] is a collection of subsets of [n], called faces, such that $\{i\} \in \Delta \ \text {for all}\ i \in [n]$ and if $X \in \Delta ~\text {and}~ Y \subseteq X$ then $Y\in \Delta$.

If $\Delta$ is a simplicial complex on the vertex set [n] and every subset of [n] belongs to $\Delta$, then $\Delta$ is called a simplex. A face $X \in \Delta$ of cardinality $|X|=m+1$ is called a face of dimension m or an m-face of $\Delta$. The dimension of $\Delta$, denoted by dim$(\Delta )$, is the maximum of dimension of all its faces.

Let $W\subseteq [n]$. We define the subcomplex $\Delta _W$ of $\Delta$ to be the simplicial complex

$$\begin{aligned} \Delta _W=\{F\in \Delta ~|~F\subseteq W\}. \end{aligned}$$

Definition 2

The Stanley–Reisner ideal of a simplicial complex $\Delta$ with vertex set $\{x_1,\ldots , x_n\}$ is a squarefree monomial ideal $\ I_\Delta$ of $R=\Bbbk [x_1, \ldots , x_n]$ generated by all monomials $x_{i_1}\cdots x_{i_j}$ such there is no face of $\Delta$ with vertices $x_{i_1},\ldots , x_{i_j}$. The quotient ring $\Bbbk [\Delta ]=R/I_\Delta$ is called Stanley-Reisner ring of the simplicial complex $\Delta$.

Remark 2.1

Let G be a finite simple graph. We can associate to G a simplicial complex $\Delta (G)$ which has faces

$$\begin{aligned} \{\{x_{i_1},\ldots , x_{i_\ell }\}~|~ \text {no}~\{x_{i_j},x_{i_k}\}~\text {is an edge of } G\}. \end{aligned}$$

One can note that the edge ideal I(G) of G is the Stanley–Reisner ideal $I_{\Delta (G)}$ of $\Delta (G)$.

The following theorem is the main tool for computing Betti numbers of Stanley–Reisner ring $\Bbbk [\Delta ]$.

Theorem 2.2

[Hochster (1975)’s Formula] The ith Betti of the Stanley–Reisner ring $\Bbbk [\Delta ]=R/I_\Delta$ is given by

$$\begin{aligned} \beta _{i,j}(\Bbbk [\Delta ])=\sum _{W\subseteq [n], |W|=j}^{}\dim _\Bbbk \widetilde{H}_{j-i-1}(\Delta _W; \Bbbk ). \end{aligned}$$

Note that if $\Delta =\Delta (G)$ for some graph G, then above formula is given as

$$\begin{aligned} \beta _{i,j}(R/I_{\Delta (G)})=\sum _{\begin{array}{c} H\subseteq G ~\text {induced}\\ |V(H)|=j \end{array}}^{}\dim _\Bbbk \widetilde{H}_{j-i-1}(\Delta (H); \Bbbk ). \end{aligned}$$

Let $G=(V,E)$ be a finite simple graph with vertex set V. A set $W\subset V$ of vertices of G is called independent or stable if no two of them are adjacent in G. We call the graph $G=(V,E)$ a bipartite graph if V can be partitioned into two disjoint and independent sets X and Y so that $V=X\cup Y$ and for any edge $e \in E(G)$, one of the vertices of e lies in X and the other in Y. We call G a complete bipartite graph of the type (|X|, |Y|) if for any vertex in X and for any vertex in Y we have an edge in E(G). A complete bipartite graph of type (m, n) is denoted by $K_{m,n}$.

Fig. 1

$K_{3,4}$

The simplicial complex $\Delta (K_{m,n})$ associated to the complete bipartite graph $K_{m,n}$ is the union of two disjoint simplices one of dimension $m-1$ and the other of dimension $n-1$. The associated simplicial complex of the complete bipartite graph $K_{3,4}$ given in Fig. 1 is pictorially given in Fig. 2.

Fig. 2

$\Delta (K_{3,4})$

We can see that $\Delta (K_{m,n})$ being the union of two disjoint simplices, the only non-zero reduced homology groups for such simplicial complexes are those in 0th position. In order to find Betti numbers of the complete bipartite graphs $K_{m,n}$, we use the simple description of associated simplicial complex $\Delta (K_{m,n})$ with Theorem 2.2.

Consider a complete bipartite graph $K_{m,n}$ with vertex set $V=\{x_1,\ldots ,x_m, y_1,\ldots ,y_n\}$, where V is partitioned into $X=\{x_1,\ldots ,x_m\}$ and $Y=\{y_1,\ldots ,y_n\}$ as independent sets. Let $\Delta =\Delta (K_{m,n})$. Suppose $\emptyset \ne W\subseteq V$ such that $W\subseteq X$ or $W\subseteq Y$, then $\Delta _W$ is a simplex and has zero reduced homology everywhere. On other hand if $W\cap X\ne \emptyset ~\text {and}~ W\cap Y\ne \emptyset$, then $\Delta _W$ is the disjoint union of two simplices. This implies that

$$\begin{aligned} \widetilde{H}_i(\Delta _W; \Bbbk )=\left\{ \begin{array}{rl} \Bbbk &{} \quad \text {if } \quad i=0\\ 0 &{} \quad \text {if }\quad i\ne 0 . \end{array}\right. \end{aligned}$$

Theorem 2.3

(Jacques 2004) The $\mathbb {N}$-graded Betti numbers of the complete bipartite graph $K_{m,n}$ is given by the expression

$$\begin{aligned} \beta _{i,j}(K_{m,n})=\left\{ \begin{array}{rl} \sum \limits _{\begin{array}{c} p+q=i+1\\ p,q\ge 1 \end{array}}^{}\left( {\begin{array}{c}m\\ p\end{array}}\right) \left( {\begin{array}{c}n\\ q\end{array}}\right) &{} \quad \text {if } \quad j=i+1\\ 0 &{} \quad \text {if } \quad j\ne i+1. \end{array}\right. \end{aligned}$$

2.2 Strongly disjoint set of bouquets

Definition 3

A graph B with vertex set $V(B)=\{x, y_1, \ldots , y_m\}$ and edge set $E(B)=\{\{x,y_i\}\mid i=1, \ldots , m\},~m\ge 1$, is called a bouquet. Thus a bouquet can also be viewed as a complete bipartite graph of type (1, m) (Fig. 3).

Fig. 3

A bouquet

The notion of bouquets for simple graphs was first introduced by Zheng (2004). Borrowing the terminology from Zheng (2004 Definition 1.7), the vertex x is called the root of B, the edges $\{x,y_i\}$stems of B, and the vertices $y_i~(1\le i\le m)$, the flowers of B. We call B a bouquet of a graph G if B is the subgraph of G. Let $\mathcal {B} = \{ B_1, B_2, \ldots , B_r \}$ be a set of bouquets of G. We fix the notations

$$\begin{aligned} \begin{aligned} R({\mathcal {B}})&= \{ x \in V(G) \; : \; x \ \text {is a root of some bouquet in }\mathcal {B} \}, \\ S({\mathcal {B}})&= \{ s \in E(G) \; : \; s \ \text {is a stem of some bouquet in } \mathcal {B} \}, \\ F({\mathcal {B}})&= \{ y \in V(G) \; : \; y \ \text {is a flower of some bouquet in }\mathcal {B} \}. \end{aligned} \end{aligned}$$

The ordered pair $(|F(\mathcal {B})|,|R(\mathcal {B})|)$ determines the type of $\mathcal {B}$. Next we define the disjointness on the set of bouquets of G.

Definition 4

(Hà and Van Tuyl 2008) A chain of length $\ell$ in a finite simple graph G with vertex set $V(G)=\{x_1, \ldots , x_n\}$ is a sequence $(e_1,e_2,\ldots , e_{\ell +1})$ of edges of G such that

• (1) $e_1, \ldots , e_{\ell +1}$ are all distinct edges of G,

• (2) $e_i=\{x_i, x_{i+1}\}$.

One can see that (2) implies $e_i\cap e_{i+1}\ne \emptyset ~\text {for}~ 1\le i\le \ell$. Two edges e and $e^\prime$ are said to be connected if there exists a chain $(e_1,\ldots , e_{\ell +1})$ where $e=e_1$ and $e^\prime =e_{\ell +1}$. If e and $e^\prime$ are two distinct edges of G, then the distance between e and $e^\prime$, denoted by $d_G(e, e^\prime )$, in G is give as

$$\begin{aligned} d_G(e,e^\prime )=min\{\ell ~{\mid }~ (e=e_1,\ldots , e_{\ell +1}=e^\prime )~ \text {is a chain} \}. \end{aligned}$$

If there is no such chain, we define $d_G(e,e^\prime )=\infty$. Two edges e and $e^\prime$ are said to be t-disjoint in G if $d_G(e,e^\prime )\ge t$. A subset $\mathcal {E}\subset E(G)$ is said to be pairwise t-disjoint if any pair of distinct edges in $\mathcal {E}$ is t-disjoint.

Remark 2.4

Let $G=(V,E)$ be finite simple graph. If $W\subseteq V$, then we define the induced subgraph $G_W$ of G on the vertex set W to be the subgraph with vertex set W and whose edge set consists of all the edges of E(G) connecting two vertices in W. Let $e_1=\{x_i,x_j\}$ and $e_2=\{x_k,x_l\}$ be two distinct edges of G, then we see that $e_1$ and $e_2$ are 3-disjoint if $\{x_i,x_j\}\cap \{x_k,x_l\}=\emptyset$ and $G_W= e_1\cup e_2$, where $W=\{x_i,x_j,x_k,x_l\}$.

Example 2.5

Let G be the graph in Fig. 4. One can see directly from Fig. 5 that the edges $e_1=\{x_1,x_2\}$ and $e_4=\{x_4,x_5\}$ are 3-disjoint in G. It is because $G_W=e_1\cup e_4$, where $W=\{x_1, x_2, x_4, x_5\}$. Whereas, Fig. 6 clearly reveals that the edges $e_4=\{x_4, x_5\}$ and $e_5=\{x_1, x_3\}$ are not 3-disjoint. This is because $G_{W^\prime }=e_3\cup e_4\cup e_5$, where $W^\prime =\{x_1, x_3, x_4, x_5\}$.

Fig. 4

G

Fig. 5

$G_W$

Fig. 6

$G_{W^\prime }$

Definition 5

(Kimura 2012) Let $\mathcal {B}=\{B_1, B_2, \ldots , B_m\}$ be a set of bouquets of G. Then we say G is strongly disjoint if the following conditions hold.

• (1) $V(B_i)\cap V(B_j)=\emptyset$ for all $i\ne j$.

• (2) We can choose a stem $s_i\in B_i$ for all $B_i\in \mathcal {B}, i=1,\ldots , m$, so that the set $\{s_1, \ldots , s_m\}$ is pairwise 3-disjoint in G.

Remark 2.6

One can see that if $\mathcal {B}=\{B_1, B_2, \ldots , B_m\}$ is a strongly disjoint set of bouquets in G, then no two vertices in $R(\mathcal {B})$ are adjacent in G. For if not, suppose the roots of bouquets $B_i$ and $B_j$ are adjacent, then for each stem of $B_1$ and for each stem of $B_2$ there exists a chain of length 2 which connects them. Thus the distance between any stem of $B_1$ and any stem of $B_2$ is 2.

Example 2.7

Consider the graph G in Fig. 7. Then one can see that G contains a bouquet $B_1$, given in Fig. 8, of type (1, 4) and a bouquet $B_2$, given in Fig. 9, of type (1, 3). Since we can choose a stem $s=\{x_1, x_2\}\in B_1~\text {and a stem}~s^\prime =\{y_1,y_2\} \in B_2$ so that $d_G({s,s^\prime })\ge 3$, we see that the set $\mathcal {B}=\{B_1,B_2\}$ of bouquets forms a strongly disjoint set of bouquets of G.

Fig. 7

G

Fig. 8

$B_1$

Fig. 9

$B_2$

Definition 6

(Kimura 2012, Definition 2.3) Let G be a finite simple graph. Then G is said to contain a strongly disjoint set of bouquets if there exists a strongly disjoint set $\mathcal {B}$ of bouquets such that $V(G)={F}(\mathcal {B})\cup {R}(\mathcal {B})$. However, If $V(G)={F}(\mathcal {B})\cup {R}(\mathcal {B})$ and $E(G)=S(\mathcal {B})$, then we say Gcoincides with strongly disjoint set$\mathcal {B}$ of bouquets.

Now before we proceed further, we recall some results due to Katzman (2006), mentioned in the introduction. For any graph G, we fix

$$\begin{aligned} \eta (G)=max\{|\mathcal {E}|~|~\mathcal {E}\subset E(G)~ \text {is a pairwise 3-disjoint in G}\}. \end{aligned}$$

Theorem 2.8

(Katzman 2006) Let G be a finite simple graph on V and $R=\Bbbk [x_1, \ldots ,x_n]$.

• (1) The graded Betti number $\beta _{i,2i}(G)$ coincides with the number of subsets W of V for which $G_W$ consists of i pairwise disjoint edges.

• (2) If there exists a subset $W\subset V$ such that $G_W$ coincides with a strongly disjoint set $\mathcal {B}$ of bouquets of type (i, j), then $\beta _{i,i+j}(G)\ne 0$.

3 Crown graphs

3.1 Crown graphs and Betti numbers

Definition 7

An n-$\textit{crown}$ graph $\mathcal {C}_{n,n}$ on 2n vertices, $n\ge 3$, is a simple graph with vertex set $V(\mathcal {C}_{n,n})=\{x_1, \ldots , x_n, y_1, \ldots , y_n\}$ and edge set $E(\mathcal {C}_{n,n})=\{\{x_i,y_j\}\mid 1\le i,j \le n~\text {and}~i\ne j\}$. It can also be considered as a subgraph of complete bipartite graph ${K}_{n,n}$ with edges of the type $\{x_i,y_i\}, 1\le i\le n$ being removed (Fig. 10).

Fig. 10

$\mathcal {C}_{3,3}$

Fig. 11

$\mathcal {C}_{4,4}$

The corresponding simplicial complex $\Delta (\mathcal {C}_{n,n})$ of an n-crown graph $\mathcal {C}_{n,n}$ is the union of two $n-1$ dimensional simplices and the n edges $\{x_i,y_i\},1\le i\le n$.

A graph G is said to be chordal if every cycle of length greater than 3 in G has a chord (an edge which is not part of the cycle). However, G is said to be weakly chordal if every cycle of length greater than 4 in G and $G^c$ (complement of G) has a chord. Crown graphs is a particular series of graphs which ceases to be Cohen-Macaulay. Crown graphs are neither chordal nor weakly chordal for they contain induced cycles of length greater than four without any chords. Moreover, they are not unmixed. One would be interested to see the relation between the combinatorial properties of crown graphs and the algebraic properties of their respective edge ideals. We shall prove some results in order to compute Betti numbers of edge ideals of crown graphs.

Theorem 3.1

Let $\mathcal {C}_{n,n}$ be an n-crown graph on vertex set $V(\mathcal {C}_{n,n})=\{x_1, \ldots , x_n, y_1, \ldots , y_n\}$. Then

$$\begin{aligned} \beta _{i,i+1}(\mathcal {C}_{n,n})=(2^{i+1}-2)\left( {\begin{array}{c}n\\ i+1\end{array}}\right) . \end{aligned}$$

Proof

From Theorem 2.2, we have

$$\begin{aligned} \beta _{i,i+1}(\mathcal {C}_{n,n})=\sum _{\begin{array}{c} W\subseteq X\cup Y\\ |W|=i+1 \end{array}}^{}\dim _\Bbbk \widetilde{H}_0(\Delta _W; \Bbbk ), \end{aligned}$$

where $X=\{x_1,\ldots , x_n\},~Y=\{y_1,\ldots y_n\}$ and $\Delta =\Delta (\mathcal {C}_{n,n})$. We know that $\widetilde{H}_0({\Delta ,\Bbbk })+1$ is the number of connected components of $\Delta _W$. Therefore, we will have a non-zero contribution to $\beta _{i,i+1}({\mathcal {C}_{n,n}})$ if the number of connected components of $\Delta _W$ is greater than one. Since $\Delta (\mathcal {C}_{n,n})$ is the union of two simplices connected by one dimensional faces of the type $\{x_k,y_k\},~1\le k\le n$, one can see that $\Delta _W$ has at most two connected components for any subset W of $V(\mathcal {C}_{n,n})$. If $W\subseteq X$ or $W\subseteq Y$, then $\Delta _W$ is a simplex and has zero reduced homology everywhere. However, if $W\subset X\cup Y$ is of the form $\{x_{r_1},\ldots , x_{r_\ell },y_{s_1},\ldots ,y_{s_m}\}$, where $\ell ,m\ge 1,~\ell +m=i+1$ and $\{r_1,\ldots , r_\ell \}~\text {and}~ \{s_1,\ldots , s_m\}$ are disjoint subsets of $\{1,\ldots , n\}$, then $\Delta _W$ consists of two connected components. This implies that $\beta _{i,i+1}(\mathcal {C}_{n,n})$ is same as the number of subsets W of $V(\mathcal {C}_{n,n})$ of the above type. One suitable subset is obtained by choosing one element (say $x_k$) from X and other i elements from $Y-\{y_k\}$. There are $\left( {\begin{array}{c}n\\ 1\end{array}}\right) \left( {\begin{array}{c}n-1\\ i\end{array}}\right)$ subsets of this type. Similarly, we get another $\left( {\begin{array}{c}n\\ 2\end{array}}\right) \left( {\begin{array}{c}n-2\\ i-1\end{array}}\right)$ subsets if we choose two elements (say $x_k, x_{k^\prime }$) from X and other $i-1$ elements from $Y-\{y_k,y_{k^\prime }\}$. Continuing this way to obtain

$$\begin{aligned} \beta _{i,i+1}(\mathcal {C}_{n,n})&=\left( {\begin{array}{c}n\\ 1\end{array}}\right) \left( {\begin{array}{c}n-1\\ i\end{array}}\right) +\left( {\begin{array}{c}n\\ 2\end{array}}\right) \left( {\begin{array}{c}n-2\\ i-1\end{array}}\right) +\cdots + \left( {\begin{array}{c}n\\ i\end{array}}\right) \left( {\begin{array}{c}n-i\\ 1\end{array}}\right) \nonumber \\&=\sum \limits _{\begin{array}{c} p+q=i+1\\ p,q\ge 1 \end{array}}\left( {\begin{array}{c}n\\ p\end{array}}\right) \left( {\begin{array}{c}n-p\\ q\end{array}}\right) . \end{aligned}$$

(3.1)

By using a well known formula

$$\begin{aligned} \sum \limits _{\begin{array}{c} r+s=m\\ r,s\ge 1 \end{array}}\left( {\begin{array}{c}n\\ r\end{array}}\right) \left( {\begin{array}{c}n-r\\ s\end{array}}\right) =(2^{m}-2)\left( {\begin{array}{c}n\\ m\end{array}}\right) , \end{aligned}$$

we can rewrite (3.1) as

$$\begin{aligned} \beta _{i,i+1}(\mathcal {C}_{n,n})=(2^{i+1}-2)\left( {\begin{array}{c}n\\ i+1\end{array}}\right) . \end{aligned}$$

$\square$

Corollary 3.2

Let $\mathcal {C}_{n,n}$ be an n-crown graph on vertex set $V(\mathcal {C}_{n,n})=\{x_1, \ldots , x_n, y_1, \ldots , y_n\}$. Then $\beta _{i,i+1}(\mathcal {C}_{n,n})=0$ for all $i\ge n$.

Proof

The proof of this result directly follows from Theorem 3.1. $\square$

Example 3.3

Let $\mathcal {C}_{4,4}$ be a 4-crown graph (given in Fig. 11) on vertex set $V(\mathcal {C}_{4,4})=\{x_1,x_2,x_3,x_4, y_1,y_2,y_3,y_4\}$. One can see that $\beta _{i,i+1}(\mathcal {C}_{4,4})=0$ for all $i\ge 4$. Using Theorem 3.1, the Betti numbers $\beta _{i,i+1},~i=1,2,3$ of $\mathcal {C}_{4,4}$ are given by

$$\begin{aligned} \beta _{1,2}(\mathcal {C}_{4,4})&=(2^2-2)\left( {\begin{array}{c}4\\ 2\end{array}}\right) =12,\\ \beta _{2,3}(\mathcal {C}_{4,4})&=(2^3-2)\left( {\begin{array}{c}4\\ 3\end{array}}\right) =24,\\ \beta _{3,4}(\mathcal {C}_{4,4})&=(2^4-2)\left( {\begin{array}{c}4\\ 4\end{array}}\right) =14. \end{aligned}$$

By using Macaulay 2 (see Grayson and Stillman 1992), the corresponding Betti table is given by

which is read as follows:

Unlike complete bipartite graphs, Hochster’s formula is somewhat daunting to use for computing all Betti numbers of crown graphs with large number of vertices because one has to compute the dimensions of all the homology groups $\widetilde{H}_{j-i-1}(\Delta _W,\Bbbk )$, where $\Delta =\Delta (\mathcal {C}_{n,n})$ and W varies over all subsets of $V(\mathcal {C}_{n,n})$ of size j. We will try to find other Betti numbers of edge ideals of crown graphs without using Hochster’s formula (Fig. 12).

Lemma 3.4

Let $\mathcal {C}_{n,n}$ be an n-crown graph on vertex set $V(\mathcal {C}_{n,n})=\{x_1, \ldots , x_n, y_1, \ldots , y_n\}$ and edge set $E(\mathcal {C}_{n,n})$. If e and $e^\prime$ are any two distinct edges in $E(\mathcal {C}_{n,n})$, then $d_{\mathcal {C}_{n,n}}(e,e^\prime )\le 3$.

Proof

Let $V=V_1\cup V_2$ be a bipartition of $V (\mathcal {C}_{n,n})$, where $V_1=\{x_1, \ldots , v_n\}$ and $V_2=\{y_1, \ldots , y_n\}$. Suppose $e=\{x_i, y_j\}~\text {and}~ e^\prime =\{x_r,y_s\}$. We will take the following cases into consideration:

Case 1. If $r=i~(\text {or}~s=j)$. Then the edges e and $e^\prime$ are adjacent with $e\cap e^\prime =\{x_i\}~(\text {or}~\{y_j\})$. Hence $d_{\mathcal {C}_{n,n}}(e,e^\prime )=1$.

Fig. 12

$\Delta (\mathcal {C}_{3,3})$

Fig. 13

$\mathcal {C}_{n,n}$

Case 2. If $s=i~\text {and}~r=j$. Then we have $e^\prime =\{x_j,y_i\}$. Since $y_j\in V_2$, there exists a vertex $x_k\in V_1,~k\ne i,j$, such that $e_2=\{x_k,y_j\}\in E(\mathcal {C}_{n,n})$. Since $k\ne i$, $x_k$ must be adjacent to $y_i$ in $V_2$ so that $e_3=\{x_k, y_i\}\in E(\mathcal {C}_{n,n})$. Also $e_3, e^\prime$ are adjacent since $e_3\cap e^\prime =\{y_i\}$. One can see from Fig. 13  that we have a chain $e=e_1, e_2, e_3,e_4=e^\prime$ of length 3 that connects e and $e^\prime$. Therefore, $d_{\mathcal {C}_{n,n}}(e,e^\prime )=3$.

Case 3. If $s\ne i~\text {and}~s\ne j~(\text {or}~ r\ne j~ \text {and}~r\ne i)$, then $x_s$ and $y_i$ (or $x_r$ and $y_j$) are adjacent. Hence $d_{\mathcal {C}_{n,n}}(e,e^\prime )=2$. $\square$

Lemma 3.5

If e and $e^\prime$ are any two distinct edges of an n-crown $\mathcal {C}_{n,n}$, then e and $e^\prime$ are 3-disjoint if and only if $e=\{x_i,y_j\}$ and $e^\prime =\{x_j,y_i\}$ for some $i,j,~1\le i,j\le n$.

Proof

The proof of this lemma directly follows from Lemma 3.4. $\square$

Theorem 3.6

Let $\mathcal {C}_{n,n}$ be an n-crown graph with vertex set $V(\mathcal {C}_{n,n})=\{x_1, \ldots , x_n, y_1, \ldots , y_n\}$ and edge set $E(\mathcal {C}_{n,n})$. If $\mathcal {E}\subset E(\mathcal {C}_{n,n})$ be a 3-disjoint subset, then $|\mathcal {E}|=2$. That is, $\eta (\mathcal {C}_{n,n})=2$.

Proof

The proof of this theorem follows from Lemmas 3.4  and 3.5. $\square$

Corollary 3.7

Let $\Gamma$ be the set of all pairwise 3-disjoint subsets of $E({C}_{n,n})$. Then $|\Gamma |=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

Proof

Let $\mathcal {E}$ be a pairwise 3-disjoint subset of $E({C}_{n,n})$. Then by Theorem 3.6, $|\mathcal {E}|=2$. Also, Lemma 3.5 guarantees us that $\mathcal {E}=\{\{x_i,y_j\}, \{x_j,y_i\}\}$ for some $1\le i\ne j\le n$. Since there are $n(n-1)$ edges in $\mathcal {C}_{n,n}$, there exists $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ subsets of $E({C}_{n,n})$ of the form $\mathcal {E}$. $\square$

Corollary 3.8

Let $\mathcal {C}_{n,n}$ be a crown graph with vertex set $V(\mathcal {C}_{n,n})=\{x_1, \ldots , x_n, y_1, \ldots , y_n\}$ and edge set $E(\mathcal {C}_{n,n})$. If there exists a strongly disjoint set of bouquets $\mathcal {B}$ of $\mathcal {C}_{n,n}$. Then $|\mathcal {B}|=2$.

Proof

Let $\mathcal {B}$ be a strongly disjoint set of bouquets of $\mathcal {C}_{n,n}$. Using Theorem 3.6, we see that if $\mathcal {E}$ is a pairwise 3-disjoint subset of $E(\mathcal {C}_{n,n})$, then $|\mathcal {E}|=2$. Therefore, if $\mathcal {B}$ strongly disjoint set of bouquets, then $|\mathcal {B}|=2$. $\square$

Theorem 3.9

Let $\mathcal {C}_{n,n}$ be an n-crown graph with vertex set $V(\mathcal {C}_{n,n})=\{x_1, \ldots , x_n, y_1, \ldots , y_n\}$ and edge set $E(\mathcal {C}_{n,n})$ and $R=\Bbbk [x_1,\ldots ,x_n, y_1,\ldots ,y_n]$, then $\beta _{2,4}(\mathcal {C}_{n,n})=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

Proof

Let $W\subset V(\mathcal {C}_{n,n})$. Using Theorem 3.6,  we note that if $G_{W}$ coincides with i disjoint edges then i is atmost equal to 2. Also, Lemma 3.5  implies that any subset $W\subset V(\mathcal {C}_{n,n})$ for which ${\mathcal {C}_{n,n}}_W$ coincides with 2 disjoint edges is of the form $\{x_i,y_j,x_j,y_i\},~ 1\le i\ne j\le n$. The number of such subsets W of $V(\mathcal {C}_{n,n})$ is equal to number of pairwise 3-disjoints subsets of $E(\mathcal {C}_{n,n})$ which, by Corollary 3.7, is equal to $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Finally, in view of Theorem 2.8 (1), one can see that $\beta _{2,4}(\mathcal {C}_{n,n})=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. $\square$

Corollary 3.10

Let $\mathcal {C}_{n,n}$ be an n-crown graph. Then $reg(\mathcal {C}_{n,n})\ge 2$.

Proof

This follows directly from Theorem 3.9 since $\beta _{2,4}(\mathcal {C}_{n,n)}\ne 0$. $\square$

4 Projective dimension of crown graphs

As mentioned earlier, the projective dimension of a module is the length of its minimal free resolution. We define the projective dimension of a graph G to be the projective dimension of the R-module $\Bbbk [\Delta (G)]=R/I(G)$, and we write $\text {pd}^{\Bbbk }(G)=\text {pd}(R/I(G))$. In general, the projective dimension of a graph will be dependent on the characteristic of our choice of the field. However in our case it is independent and we write the projective dimension of G as pd(G). In this section we find the projective of the crown graph $\mathcal {C}_{n,n}$.

4.1 Dominations parameters of graphs

Let $G=(V,E)$ be a finite simple graph. We define the neighborhood of a vertex $u\in V$ to be the set $N_G(u)=\{v\in V~|~\{u,v\}\in E\}$. For a subset $U\subset V$, we define the open neighborhood of U to be the set $N_G(U)=\cup _{u\in U}N_G(u)$ and the closed neighborhood of U is the set $N_G[U]=N_G(U)\cup U$. Furthermore, if $F\subseteq E$, we write $N_G[F]$ for the set $N_G[V(F)]$, where V[F] is the set of vertices of the edges in F.

A dominating set for G is a subset $U\subseteq V$ such that $N_G[V]=V(G)$. The minimum size $\gamma (G)$ of all dominating sets for G is called domination number, whereas the maximum size $\Gamma (G)$ of a minimal dominating set is called upper domination number of G. We define the independent domination numberi(G) of G as

$$\begin{aligned} i(G)=\text {min}\{|A|~|~A\subseteq V(G)~ \text {is independent and dominating set}\}. \end{aligned}$$

Let $X,Y\subseteq V(G)$. We say X dominates Y in G if $Y\subseteq N_G(X)$. Let $\gamma (Y,G)$ denotes the least size of a subset X that dominates Y in G. We define the independence domination number$\tau (G)$ as

$$\begin{aligned} \tau (G)=\text {max}\{\gamma (A, G^\circ )~|~ A\subseteq V(G^\circ ) \text { is an independent set}\}, \end{aligned}$$

where $G^\circ$ is the graph obtained from G by removing the isolated vertices. Independence domination number was first introduced by Aharoni et al. (2002).

A vertex $v\in V(G)$ is said to vertex-wise dominate an edge $e\in E(G)$ if $v\in N_G[e]$. We call a set $W\subseteq V(G)$ a vertex-wise dominating set, if for each edge $e\in E(G)$ there exists a vertex $w\in W$ that vertex-wise dominates e. However, an edge $e\in E(G)$ is said to edge-wise dominate a vertex $v\in V(G)$ if $v\in N_G[e]$. We call a set $F\subseteq E(G)$ an edge-wise dominating set, if for each vertex $v\in V(G^\circ )$ there exists an edge $e^\prime \in F$ that edge-wise dominates v. The edge-wise domination number$\epsilon (G)$ is defined as

$$\begin{aligned} \epsilon (G)=\text {min}\{|F|~|~F\subseteq E(G)~ \text {is an edge dominating set}\}. \end{aligned}$$

Theorem 4.1

(Dao and Schweig 2013) For any graph $G=(V,E)$,

$$\begin{aligned} |V(G)|-i(G)\le pd(G)\le |V(G)|-max\{\tau (G),\epsilon (G)\}. \end{aligned}$$

Lemma 4.2

Let $\mathcal {C}_{n,n}$ be an n-crown graph on vertex set $V(\mathcal {C}_{n,n})=X\cup Y$, where $=X\{x_1,\ldots ,x_n\}$ and $Y=\{ y_1,\ldots ,y_n\}$. Then,

• (1) the independent domination number $i(\mathcal {C}_{n,n})$ of $\mathcal {C}_{n,n}$ is two,

• (2) the independence domination number $\tau (\mathcal {C}_{n,n})$ of $\mathcal {C}_{n,n}$ is two,

• (3) the edge-wise domination number $\epsilon (\mathcal {C}_{n,n})$ of $\mathcal {C}_{n,n}$ is two.

Proof

• (1) One can see that the only independent and dominating sets of $\mathcal {C}_{n,n}$ are X, Y and $\{x_i,y_i\},1\le i\le n$. Therefore, we conclude that the independent domination number $i(\mathcal {C}_{n,n})$ of $\mathcal {C}_{n,n}$ is two.

• (2) If A is an independent set of $\mathcal {C}_{n,n}$, then either A is of the form $\{x_i,y_i\},~1\le i\le n$ or $A\subseteq X, Y$. For if $A=\{x_i,y_i\}, 1\le i\le n$, then $\gamma (A,\mathcal {C}_{n,n})=2$. Suppose $A\subseteq X,Y$, then it is not hard to see that $\gamma (A,\mathcal {C}_{n,n})=2$. Hence, in either case $\gamma (A,\mathcal {C}_{n,n})=2$ for any independent set A of $\mathcal {C}_{n,n}$. Therefore, we conclude that $\tau (\mathcal {C}_{n,n})$ is two.

• (3) It is not hard to see that any two distinct edges in $E(\mathcal {C}_{n,n})$ will form an edge-wise dominating set of $\mathcal {C}_{n,n}$. Furthermore, the set $\{x_i,y_i\}, 1\le i\le n$ being an independent set, we conclude that $\epsilon (\mathcal {C}_{n,n})=2$. $\square$

Theorem 4.3

Let $\mathcal {C}_{n,n}$ be a n-crown graph. Then pd$(\mathcal {C}_{n,n })=2n-2$.

Proof

The proof of this theorem directly follows from Theorem 4.1 and Lemma 4.2. $\square$