\section{Introduction}
\sloppy In this work, let $G$ be a finite simple graph (or just a graph) with the set of vertices $V(G)=\{x_1,\dots,x_n\}$ and edges $E(G)=\left\{\{x_i,x_j\}\mid x_i\mbox{ is adjacent to }x_j\right\}$. Let $R=\K[x\mid x\in V(G)]$ be a polynomial ring over a field $\K$.  
Villarreal  associated  an ideal $I(G)$ generated by the set of  monomials $\{x_ix_j\mid \{x_i,x_j\}\in E(G)\}$ in $R$ to the graph $G$,  see~\cite{Villarreal1990}. 
The ideal $I(G)$ is called the \emph{edge ideal} of the graph $G$ and the quotient ring $R/I(G)$ is called Stanley-Reisner ring \cite{Stanley1979}. This association reveals a strong connection  between algebraic properties and invariants of $R/I(G)$ on one side and combinatorial properties and invariants of $G$ on the the other side.
To be more precise,  there is a great interest in finding the regularity and projective dimension of $R/I(G)$ by having some information about $G$, see \cite{GitlerValencia2005, Kimura2012, MoradiKiani2010, Zheng2004}. In \cite{EliahouVillarreal1999}, Eliahou and Villarreal in 1998 tried to find a relation between the pojective dimension of $R/I(G)$ and a maximum degree of a graph $G$ for a certain class of graphs. They proposed the following conjecture (see {\cite[Conjecture 4.13]{GitlerValencia2005}}).
\begin{conjecture}\label{conjecture 1}
\begin{center}
If the edge ideal of a connected graph $G$ has 2-linear resolution, then the projective dimension $R/I(G)$ is equal to the maximum degree of vertices of $G$.
\end{center}
\end{conjecture}
This conjecture is not true in general. Indeed, in this paper we show that the difference between the projective dimension and the maximum degree of a graph need not be bounded even for co-chordal graphs, see section \ref{section}. There are some attempts to prove the conjecture  for some special cases. Gitler and Valencia in \cite{GitlerValencia2005} show that the conjecture holds for some graphs in a class of graphs in which the graph and its complement are both chordal. Fr\"oberg in \cite{Froberg1990} defines $d$-tree and generalized $d$-tree graphs. The generalized $d$-tree graphs are exactly the chordal graphs. In \cite{MoradiKiani2010}, Moradi and Kiani proved the conjecture when the complement of $G$ is a $d$-tree. Let $(d_1,d_2,\dots,d_q)$ be a non-increasing sequence of positive integers. In this paper we define the concept of $(d_1,d_2,\dots,d_q)$-tree graphs and show that all $d$-tree graphs are $(d_1,d_2,\dots,d_q)$-tree and $(d_1,d_2,\dots,d_q)$-tree graphs are chordal, that is
$$d\mbox{-tree graphs }\Rightarrow(d_1,d_2,\dots,d_q)\mbox{-tree graphs }\Rightarrow\mbox{ chordal graphs}$$
and the converse of the above implications may not hold in general. The graphs define by Gitler and Valencia are also $(d_1,d_2,\dots,d_q)$-tree. In Theorem \ref{d-tree VD} we prove that all $(d_1,d_2,\dots,d_q)$-tree graphs are vertex decomposable. Morey and Villarreal in \cite{MoreyVillarreal2012} show that for any graph $G$ the big height of $I(G)$ is a lower bounded for projective dimension $R/I(G)$ and the equality holds if $G$ is sequentially Cohen-Macaulay. In Theorem \ref{pdim max} we prove that the maximum degree of vertices any $G$ is a lower bounded of the big height of $I(G)$. In other words, the maximum degree of vertices is another lower bounded for projective dimension of any graph and the equality holds if the graph has a full vertex or it is the complement of a $(d_1,d_2,\dots,d_q)$-tree, see Theorems \ref{pdim G1 empty} and \ref{d-tree pdim}. Our Theorem \ref{pdim G1 empty} generalises the results of Gitler and Valencia in \cite{GitlerValencia2005}  and  Moradi and Kiani \cite{MoradiKiani2010} on Eliahou and Villarreal conjecture.  



\section{Preliminaries}
A \emph{simplicial complex} $\Delta$ on the vertex set $V=\{x_1,\ldots,x_n\}$ is a collection of subsets of $V$ such that
\begin{enumerate}
	\item[i)] $\{x_i\}\in\Delta$ for every $1\leq i\leq n$ and
	\item[ii)] if $F\in\Delta$ and $H\subseteq F$, then $H\in\Delta$. 
\end{enumerate}
An element $F$ of $\Delta$ is  a \emph{face} of $\Delta$ and a maximal (with respect to inclusion) face is a \emph{facet}. The set of all facets of $\Delta$ is denoted by $\mathcal{F}(\Delta)$ and we sometimes write $\lr{F\mid F\in\mathcal{F}(\Delta)}$ for $\Delta$. A simplicial complex $\Delta$ is called \emph{pure} if the facets have the same cardinality. Let $d=\max\{|F|\mid F\in\Delta\}$, the \emph{dimension} of $\Delta$ is $\dim\Delta=d-1$. The \emph{Stanley-Reisner ideal} of $\Delta$ is $$I_\Delta=\lr{x_F\mid F\notin\Delta}$$ 
where $x_F=\prod_{x_i\in F}x_i$. The quotient algebra $\K[\Delta]=R/I_{\Delta}$ is the \emph{Stanley-Reisner ring} of $\Delta$ over a field $\K$. The Krull dimension of $\K[\Delta]$ is $\dim\K[\Delta]=\dim\Delta+1$.
A simplicial complex with only one facet is a \emph{simplex}.
Let $f_i=f_i(\Delta)$ be the number of faces of $\Delta$ of cardinality $i+1$. The sequence $f(\Delta)=(f_{-1}=1,f_0,f_1,\dots,f_{d-1})$ is the \emph{$f$-vector} of $\Delta$. The \emph{$h$-vector} $h(\Delta)=(h_0,h_1,\dots,h_d)$ of $\Delta$ can be computed in terms of $f$-vector as follows:
\begin{equation}\label{eq h_i}
	h_i=\sum_{j=0}^{i}(-1)^{i-j}\binom{d-j}{d-i}f_{j-1},\quad 0\leq i\leq d.
\end{equation}
The \emph{Hilbert series} of $\K[\Delta]$ is of the form $H_{\K[\Delta]}(t)=(h_0+h_1t+\dots+h_st^s)/(1-t)^d$. The \emph{Hilbert polynomial}  of $\K[\Delta]$ is $P_{\K[\Delta]}(t)=h_0+h_1t+\dots+h_st^s$ with $h_s\neq0$. The \emph{$a$-invariant} $a(\K[\Delta])$ is the degree of rational function $H_{\K[\Delta]}(t)$, that is, $s-d$.

A \emph{subcomplex} $\Gamma$ of $\Delta$ is a simplicial complex whose facets are faces of $\Delta$. If $F \in \Delta$ is a face, then the \emph{deletion} of $F$ is the subcomplex
$$\del_{\Delta}(F)=\{E\in\Delta\mid E\cap F= \emptyset\},$$
of $\Delta$ and the \emph{link} of $F$ is the subcomplex of $\Delta$ and defined by
$$\link_{\Delta}(F)=\{E\in\Delta\mid E\cap F=\emptyset\text{ and }E\cup F\in\Delta\}.$$

Let $G$ be a graph and $I(G)$ the edge ideal of $G$ as defined in the introduction section.  A \emph{path} $P_k$ of length $k$ in $G$ is a sequence of distinct vertices $x_{i_0}, x_{i_1}, \dots, x_{i_k}$ and a sequence of edges $\{x_{i_j}, x_{i_{j+1}}\}\in E(G)$. A \emph{cycle}  of length $k$ in $G$ is a path $P_k$ together with the edge $\{x_{i_k}, x_{i_0}\}$. 
A \emph{connected} graph $G$ is a graph that has a path between every pair of vertices, and disconnected otherwise.
 The \emph{neighbourhood} of a vertex $x\in V(G)$ is the set $N_G(x)=\{x_j\in V(G)\mid x\mbox{ is adjacent to }x_j\}$. 
 For any subset $F\subseteq V(G)$, the set of neighbourhood of $F$ is $N_G(F)=\bigcup_{x\in F}N_G(x)$. The \emph{closed neighbourhood} of $F$ is $N_G[F]=N_G(F)\cup F$. The \emph{degree} of a vertex $x\in V(G)$ is defined to be $\deg_G(x)=|N_G(x)|$. An \emph{isolated} vertex of $G$ is a vertex of degree zero.
 A graph $H$ is a \emph{subgraph} of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. An \emph{induced subgraph} on $S\subseteq V(G)$ is a subgraph $G_S$ of $G$ such that $\{x_i,x_j\}\in E({G_S})$ if $\{x_i,x_j\}\in E(G)$ for all $x_i,x_j\in S$. The subgraph $G\backslash S$ is obtained by removing all the vertices of $S$ from $G$ and any edge which has at least one of its endpoints in $S$. We write $G\backslash x$ instead of $G\backslash\{x\}$ if $S$ consists of a single vertex $x$. The \emph{complement} of a graph $G$ is the graph $\overline{G}$ such that $V(G)=V({\overline{G}})$ and $E({\overline{G}})=\{\{x_i,x_j\}\mid \{x_i,x_j\}\notin E(G)\}$. A subset $C \subseteq V(G)$ is called a \emph{vertex cover} of $G$ if every edge of $G$ has one its endpoints in $C$.  A vertex cover is \emph{minimal} if it is minimal with respect to set inclusion among the set of vertex covers $G$. A graph $G$ is \emph{unmixed} if all minimal vertex covers have the same cardinality. A subset $F\subseteq V(G)$ is called an \emph{independent} set of $G$ if no two vertices in $F$ are adjacent. An independent set $F$ is \emph{maximal} if it is not contained in any other independent set. A graph $G$ is well-covered if all maximal independent sets have the same cardinality. Hence, a graph $G$ is unmixed if and only if it is well-covered. A subset $K\subseteq V(G)$ is a \emph{clique} of $G$ if every two distinct vertices of $K$ are adjacent in $G$. A \emph{complete graph} $\mathcal{K}_r$ is a clique on $r$ vertices.The \emph{independence complex} $\Delta_G$ of $G$ is the set of all independent sets of $G$, that is $$\Delta_G=\{F\subseteq V(G)\mid F\text{ is an independent set in }G\}.$$
In this case $I_{\Delta_G}=I(G)$. The \emph{clique complex} $\Delta(G)$ of $G$ consists all the clique sets of $G$, that is $$\Delta(G)=\{K\subseteq V(G)\mid K\text{ is a clique set of }G\}.$$
Note that the independent simplicial complex of a graph $G$ is the clique complex of $\overline{G}$. Hence $\Delta_G=\Delta(\overline{G})$. Further, a graph $G$ is unmixed if and only if $\Delta_G$ is pure. An \emph{induced $k$-cycle} $C_k$ in $G$ is cycle of length $k$ such that $G_{V(C_k)}=C_k$. A graph $G$ is called \emph{chordal} if it does not contain any $C_k$, $k\geq4$. A graph $G$ is  \emph{co-chordal} if $\overline{G}$ is chordal.

Consider the following minimal graded free resolution of $\K[\Delta_G]=R/I(G)$ over $R$
$$
0 \longrightarrow \bigoplus_{j} R(-j)^{\beta_{p, j}} \longrightarrow \cdots \longrightarrow \bigoplus_{j} R(-j)^{\beta_{1, j}}\longrightarrow \bigoplus_{j} R(-j)^{\beta_{0, j}} \longrightarrow R \longrightarrow\K[\Delta_G] \longrightarrow 0
$$
where $R(-j)$ denotes the $R$-module obtained by shifting the degrees of $R$ by $j$.
The integer $\beta_{i, j}(\K[\Delta_G]):=\beta_{i, j}$ is called the $i^{th}$ graded Betti number of $\K[\Delta_G]$ in degree $j$. The length $p$ of the resolution is called the \emph{projective dimension} of $\K[\Delta_G]$ over $R$, that is
$$
\pdim\K[\Delta_G]=\max \left\{i\mid \beta_{i, j}(\K[\Delta_G]) \neq 0 \text { for some } j\right\} \text {. }
$$
The (Castelnuovo–Mumford) \emph{regularity} of $\K[\Delta_G]$ over $R$ is $$\reg\K[\Delta_G]=\max\{j-i\mid \beta_{i,j}(\K[\Delta_G])\neq0\}.$$

The 2-linear resolution (over $R$) of $\K[\Delta_G]$ is the minimal graded free resolution of the form
$$
0 \longrightarrow R(-2-p)^{\beta_{p}} \longrightarrow \cdots\longrightarrow R(-3)^{\beta_{1}} \longrightarrow R(-2)^{\beta_{0}} \longrightarrow R \longrightarrow\K[\Delta_G] \longrightarrow 0.
$$

In \cite{Froberg1990}, Fr\"oberg prove that $\K[\Delta_G]$ has a 2-linear resolution if and only if $G$ is co-chordal. We refer the reader to \cite{HerzogHibi2011, Stanley1996, Villarreal2015} for further details regarding the terminologies in this section.


\section{A counterexample to the conjecture}\label{section}
In this section we give an example which shows the conjecture of Eliahou and Villarreal does not hold in general. The conjecture states that $$\pdim\K[\Delta_G]=\displaystyle\max_{1\leq i \leq n}\left\{\deg_{G}(x_i)\right\},$$ whenever $G$ is connected and it is the complement of a co-chordal graph.
Indeed, the difference between the projective dimension and a maximum degree of a graph may not be bounded in general. The following inequality is well known (see {\cite[Corollary B.4.1]{Vasconcelos1998}})
\begin{equation}\label{eq1}
\deg P_{\K[\Delta_G]}(t)-\reg\K[\Delta_G]\leq\dim\K[\Delta_G]-\dep\K[\Delta_G]
\end{equation}
and the equality holds if $\K[\Delta_G]$ has 2-linear resolution. Hence the equality holds in Equation \eqref{eq1} if $G$ is a co-chordal graph.

The \emph{$r$-barbell} graph is a chordal graph obtained by connecting two copies of a complete graph $\mathcal{K}_r$ by a bridge, for example see Figure \ref{fig1}.
\begin{figure}[ht]
	\begin{center}
		\begin{tikzpicture}[x = 2cm, y = 1.5cm]
			\draw[fill] (0,0) circle [radius = 0.04];
			\draw[fill] (.75,1) circle [radius = 0.04];
			\draw[fill] (1.5,0) circle [radius = 0.04];
			\draw[fill] (.75,-1) circle [radius = 0.04];
			\draw[fill] (2.25,0) circle [radius = 0.04];
			\draw[fill] (3,1) circle [radius = 0.04];
			\draw[fill] (3.75,0) circle [radius = 0.04];
			\draw[fill] (3,-1) circle [radius = 0.04];
			
			\draw (0,0)--(.75,1)--(1.5,0)--(.75,-1)--(0,0);
			\draw (0,0)--(1.5,0);
			\draw (.75,1)--(.75,-1);
			\draw (2.25,0)--(3,1)--(3.75,0)--(3,-1)--(2.25,0);
			\draw (1.5,0)--(2.25,0);
			\draw (2.25,0)--(3.75,0);
			\draw (3,1)--(3,-1);
			
		
		
						\node[above right=-.05] at (1.5,0) {$x_1$};
		
						\node[above left=-.05] at (2.25,0) {$x_2$};
		
		
		
		\end{tikzpicture}
	\end{center}
	\caption{The $4$-barbell graph.}
	\label{fig1}
\end{figure}

For $r\geq3$, let $G$ be the complement of the $r$-barbell graph. Then the independence complex of $G$ is $\Delta_G=\lr{V(\mathcal{K}_r),V(\mathcal{K}_r),\{x_1,x_2\}}$ on $|V(G)|=2r$. The $f$-vector of $\Delta_G$ is $\left(1,2\binom{r}{1},2\binom{r}{2}+1,2\binom{r}{3},2\binom{r}{4},\dots,2\right)$ and $\dim\K[\Delta_G]=r$. From Equation \eqref{eq h_i} one can find $h_{r}=0$ and $h_{r-1}=(-1)^{r-1}(-2)$ after some simple calculations. Hence $h_{r-1}\neq0$ and so the degree of Hilbert polynomial of $\K[\Delta_G]$ is $\deg P_{\K[\Delta_G]}(t)=r-1$. Thus the equality of Equation \eqref{eq1} gives $\dep\K[\Delta_G]=r-(r-1)+1=2$. The Auslander-Buchsbaum formula $\pdim\K[\Delta_G]+\dep\K[\Delta_G]=\dim R$ in \cite{AuslanderBuchsbaum1957} implies $\pdim\K[\Delta_G]=2r-2$. Note that $\max_{1\leq i \leq 2r}\left\{\deg_{G}(x_i)\right\}=r$. Therefore
 $$\pdim\K[\Delta_G]-\displaystyle\max_{1\leq i \leq 2r}\left\{\deg_{G}(x_i)\right\}=r-2.$$



\section{Main results}
In this section we show that  the maximum degree of vertices of any graph $G$ is a lower bounded of $\pdim\K[\Delta_G]$. Further,  a sufficient condition for which $\pdim\K[\Delta_G]=\max_{1\leq i \leq n}\left\{\deg_{G}(x_i)\right\}$ is given. The main results in this section are Theorems \ref{pdim max}, \ref{pdim G1 empty}, \ref{d-tree VD}, and \ref{d-tree pdim}. We start by proving the following standard Lemma:
\begin{lemma}
	Let $G$ be a graph and $F\subseteq V(G)$. Then $F$ is a maximal independent set of $G$ if and only if $N_G[F]=V(G)$ and $F\cap N_G(F)=\emptyset$.
	\label{max ind}
\end{lemma}
\begin{proof}
	($\Rightarrow$)	Let $F$ be a maximal independent set. Then $V(G)\backslash F$ is the set of all neighbourhoods of $F$. Hence $F\cup N_G(F)=V$ and $F\cap N_G(F)=\emptyset$.
	
	($\Leftarrow$) Let $v\in F$. Then $v\notin N_G(F)$ since $F\cap N_G(F)=\emptyset$. Thus there is no edge between the vertices of $F$. Therefore $F$ is an independent set. Now suppose there is an independent set $A$  in $G$ with $F\subsetneq A$. Let $a\in A\backslash F$. Then $a\in N_G(F)$ and so $\{a,v_i\}$ is an edge for some $v_i\in F$. Hence $F\cup\{a\}\subseteq A$ is not an independent set in $G$ which is contradiction. Therefore $F$ is maximal. 
\end{proof}
\begin{definition}\label{graph G_i}
	Let $F=\{v_1,\dots,v_r\}$ be an ordered independent set of a graph $G$. For $1\leq i\leq r$, the graph $G_i$ is obtained from $G$ inductively as follows:
	\begin{enumerate}
		\item[i)] $G_0=G$,
		\item[ii)] $G_{i}=G_{i-1}\backslash{N_{G_{i-1}}[v_i]}$.
	\end{enumerate}
\end{definition}

\begin{remark}
	From the  Definition~\ref{graph G_i} we note that $N_G(F)=\bigcup_{i=1}^{r}N_{G_{i-1}}(v_i)$ and $N_{G_{i-1}}(v_i)\cap N_{G_{j-1}}(v_j)=\emptyset$ for $1\leq i<j\leq r$.
\end{remark}

\begin{example}\label{example 1}
	Consider the graph $G$ in Figure~\ref{Gi-process}. Choose an independent set, say $F=\{x_1,x_5\}$. One can choose $v_1=x_1$ and $v_2=x_5$. This order is chosen for the sake of illustration, one can choose another order but in this case the $G_i$s may differ. Then the graph $G$, $G_1=G\backslash{N_G[x_1]}$ and $G_2=G_1\backslash{N_{G_1}[x_5]}$ are illustrated in  Figure~\ref{Gi-process}.
	\begin{figure}[ht]
		\begin{subfigure}{.4\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0,0) circle [radius = 0.04];
					\draw[fill] (.75,.75) circle [radius = 0.04];
					\draw[fill] (.75,0) circle [radius = 0.04];
					\draw[fill] (.75,-.75) circle [radius = 0.04];
					\draw[fill] (1.5,0) circle [radius = 0.04];
					\draw[fill] (2.25,0) circle [radius = 0.04];
					\draw[fill] (1.5,-.75) circle [radius = 0.04];
					
					\draw (0,0)--(.75,.75)--(.75,0)--(.75,-.75)--(0,0);
					\draw (.75,.75)--(1.5,0)--(.75,-.75);
					\draw (.75,0)--(1.5,0)--(2.25,0);
					\draw (.75,.75)--(2.25,0);
					\draw (.75,-.75)--(2.25,0);
					\draw (.75,0)--(1.5,-.75);
					\draw (2.25,0)--(1.5,-.75);
					
					\node[left] at (0,0) {$x_1$};
					\node[above] at (.75,.75) {$x_2$};
					\node[left] at (.75,0) {$x_3$};
					\node[below] at (.75,-.75) {$x_4$};
					\node[above right=-.08] at (1.5,0) {$x_5$};
					\node[right] at (2.25,0) {$x_6$};
					\node[below] at (1.5,-.75) {$x_7$};
				\end{tikzpicture}
				\caption*{The graph $G$.}
			\end{center}
		\end{subfigure}
		\begin{subfigure}{.3\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				
				
					\draw[fill] (.75,0) circle [radius = 0.04];
				
					\draw[fill] (1.5,0) circle [radius = 0.04];
					\draw[fill] (2.25,0) circle [radius = 0.04];
					\draw[fill] (1.5,-.75) circle [radius = 0.04];
					
				
				
					\draw (.75,0)--(1.5,0)--(2.25,0);
				
				
					\draw (.75,0)--(1.5,-.75);
					\draw (2.25,0)--(1.5,-.75);
					
				
					\node[above] at (.75,.75) {$~$};
					\node[above] at (.75,0) {$x_3$};
				
					\node[above] at (1.5,0) {$x_5$};
					\node[above] at (2.25,0) {$x_6$};
					\node[below] at (1.5,-.75) {$x_7$};
				\end{tikzpicture}
				\caption*{The graph of $G_1$.}
			\end{center}
		\end{subfigure}
	\begin{subfigure}{.25\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
			
			
			
			
			
			
				\draw[fill] (1.5,-.75) circle [radius = 0.04];
				
			
			
			
			
			
			
			
				
			
				\node[above] at (.75,.75) {$~$};
			
			
			
			
				\node[below] at (1.5,-.75) {$x_7$};
			\end{tikzpicture}
			\caption*{The graph of $G_2$.}
		\end{center}
	\end{subfigure}
		\caption{}\label{Gi-process}
	\end{figure}
\end{example}

\begin{lemma}\label{max-process}
	Let $G$ be a graph and $F=\{v_1,\dots,v_r\}$ be an independent set of $G$. Then $G_r=\emptyset$ if and only if $F$ is a maximal independent set of $G$.
\end{lemma}
\begin{proof}
	We have $G_r=G_{r-1}\backslash N_{G_{r-1}}[v_r]=G\backslash N_{G}[F]$. Then $G_r=\emptyset$ if and only if $\emptyset=G\backslash N_{G}[F]$ if and only if $N_G[F]=V(G)$. Now the assertion follows from Lemma \ref{max ind}.
\end{proof}
 
\begin{lemma}
	Let $G$ be a graph. If $F=\{v_1,\dots,v_r\}$ is a maximal independent set of $G$. Then $ |N_{G}(F)|=\sum_{i=1}^{r}\deg_{G_{i-1}}(v_i).$
	\label{deg neighbourhood}
\end{lemma}
\begin{proof}
	For $1\leq i\leq r$, from the construction of $G_i$s and Lemma \ref{max-process} we have $G_r=\emptyset$ and $V(G)=N_{G}(v_1)\cup N_{G_1}(v_2)\cup\dots\cup N_{G_{r-1}}(v_r)\cup F$. Comparing with Lemma \ref{max ind} we get that $N_G(F)=\bigcup_{i=1}^{r}N_{G_{i-1}}(v_i)$. Thus $|N_G(F)|=\sum_{i=1}^{r}\deg_{G_{i-1}}(v_i)=n-r$.
\end{proof}
\begin{remark}
	We note that $F\in\mathcal{F}(\Delta_G)$ has maximum (minimum) cardinality if and only if  $\sum_{i=1}^{r}\deg_{G_{i-1}}(v_i)$ is minimum (maximum).\\
\end{remark}

\begin{definition}
	For $1\leq i\leq r$, a \emph{max-process} is a procedure that produces an  ordered independent subset $F$ of $V(G)$   as   follows:
	\begin{enumerate}
		\item[i)] $F_1=\{v_1\in V(G)\mid\deg_G(v_1)\text{ is maximum}\}\text{ and }G_1=G\backslash N_G[v_1]$,
		\item[ii)] $F_i=F_{i-1}\bigcup\left\{v_i\in V(G)\mid \deg_{G_{i-1}}(v_i)\text{ is maximum}\right\}\text{ and }G_i=G_{i-1}\backslash N_{G_{i-1}}[v_i]$,
		\item[iii)] $F=F_r$.
	\end{enumerate}
\end{definition}

By Lemma \ref{max-process} we note that the set $F$ in the definition of max-process is a maximal independent set of $G$ if and only if $G_r=\emptyset$.

\begin{example}\label{example 3}
	Consider the graph $G$ given in Figure \ref{fig8}. Note that for $i=2,3,4,5,6$ $\deg_{G}(x_i)$ is maximum in $G$.
	If  $v_1=x_3$, then $F_1=\{x_3\}$ and $G_1=G\backslash N_G[x_3]$. Now the vertices  $x_1$ and $x_2$ are of degree zero in $G_1$. We have two options for $v_2$, set $v_2=x_1$. Then $F_2=\{x_3,x_1\}$ and $G_2=G_1\backslash N_{G_1}[x_1]$. Finally, let $v_3=x_6$. Then   $F=\{x_3,x_1,x_6\}$ and $G_3=\emptyset$. Thus by Lemma \ref{max-process} $F$ is a maximal independent set of $G$.
	\begin{figure}[ht]
		\begin{subfigure}{.35\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0,0) circle [radius = 0.04];
					\draw[fill] (.75,.75) circle [radius = 0.04];
					\draw[fill] (.75,0) circle [radius = 0.04];
					\draw[fill] (.75,-.75) circle [radius = 0.04];
					\draw[fill] (1.5,0) circle [radius = 0.04];
					\draw[fill] (2.25,0) circle [radius = 0.04];
					\draw[fill] (1.5,-.75) circle [radius = 0.04];
					
					\draw (0,0)--(.75,.75)--(.75,0)--(.75,-.75)--(0,0);
					\draw (.75,.75)--(1.5,0)--(.75,-.75);
					\draw (.75,0)--(1.5,0)--(2.25,0);
					\draw (.75,.75)--(2.25,0);
					\draw (.75,-.75)--(2.25,0);
					\draw (.75,0)--(1.5,-.75);
					\draw (2.25,0)--(1.5,-.75);
					
					\node[left] at (0,0) {$x_1$};
					\node[above] at (.75,.75) {$x_2$};
					\node[left] at (.75,0) {$x_3$};
					\node[below] at (.75,-.75) {$x_4$};
					\node[above right=-.08] at (1.5,0) {$x_5$};
					\node[right] at (2.25,0) {$x_6$};
					\node[below] at (1.5,-.75) {$x_7$};
				\end{tikzpicture}
				\caption*{The graph $G$.}
			\end{center}
		\end{subfigure}
		\begin{subfigure}{.37\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0.75,0) circle [radius = 0.04];
					\draw[fill] (2.25,0) circle [radius = 0.04];
					
					\node[below] at (0.75,0) {$x_1$};
					\node[below] at (2.25,0) {$x_6$};
				\end{tikzpicture}
				\caption*{The graph of $G_1$.}
			\end{center}
		\end{subfigure}
		\begin{subfigure}{.25\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (2.25,0) circle [radius = 0.04];
					
					\node[below] at (2.25,0) {$x_6$};
				\end{tikzpicture}
				\caption*{The graph of $G_2$.}
			\end{center}
		\end{subfigure}
	\caption{}\label{fig8}
	\end{figure}
\end{example}

The \emph{big height} $\bight I(G)$ of an edge ideal $I(G)$ is the maximum cardinality of minimal vertex covers of $G$, equivalently, the cardinality of a set whose complement of a maximal independent set of minimum cardinality. The following bound on the projective dimension of $\K[\Delta_G]$ is proved by Moray and Villarreal in  Corollary 3.33 \cite{MoreyVillarreal2012}. For any graph $G$ we have  $$\pdim\K[\Delta_G]\geq\bight I(G)$$ and the equality holds if $\K[\Delta_G]$ is sequentially Cohen-Macaulay (see {\cite[Definition 2.9]{Stanley1996}} for the definition of sequentially Cohen-Macaulay). The following theorem gives a lower bounded for big height of the edge ideal of any graph.
\begin{theorem}\label{pdim max}
	Let $G$ be a graph. Then $\displaystyle\pdim\K[\Delta_G]\geq\bight I(G)\geq\max_{1\leq i \leq n}\{\deg_G(x_i)\}.$
\end{theorem}
\begin{proof}
	Let $F=\{v_1,\dots,v_r\}$ be a maximal independent set  produced by $\max$-process. Then $s\leq r\leq d$ where $s$ is the minimum cardinality of a maximal independent set and $\dim\K[\Delta_G]=d$. By the definition of $F$ we have $\max_{1\leq i \leq n}\{\deg_G(x_i)\}=\deg_{G}(v_1)$. By Lemma \ref{deg neighbourhood} we have $\deg_G(v_1)\leq\sum_{i=1}^{r}\deg_{G_{i-1}}(v_i)=|N_G(F)|=n-r$ since $F$ is a maximal independent set. By {\cite[Corollary 3.33]{MoreyVillarreal2012}} we have that $\pdim\K[\Delta_G]\geq\bight I(G)=n-s\geq n-r\geq\max_{1\leq i \leq n}\{\deg_G(x_i)\}$.
\end{proof}

In the rest of this section we provide two different sufficient conditions on $G$ for which $\pdim\K[\Delta_G]=\max_{1\leq i \leq n}\{\deg_G(x_i)\}.$ The first class of graphs for which the equality holds is the class of graphs with a  full-vertex. A vertex $x\in V(G)$ is called a \emph{full-vertex} if $N_G[x]=V(G)$. A full-vertex is also known  as a universal vertex or a dominating vertex.
\begin{theorem}\label{pdim G1 empty}
	Let $G$ be a graph with a full-vertex $x$. Then $$\displaystyle\pdim\K[\Delta_G]=\max_{1\leq i \leq n}\{\deg_G(x_i)\}=n-1.$$
	\end{theorem}
\begin{proof}
	By Lemma \ref{max-process}, $F=\{x\}$ is a maximal independent set with minimum cardinality. Lemma \ref{deg neighbourhood} implies that $ |N_G(x)|=\deg_{G}(x)=\max_{1\leq i \leq n}\{\deg_{G}(x_i)\}=n-1$. Using Theorem \ref{pdim max} we have $\pdim\K[\Delta_G]\geq\bight I(G)=n-1$. We claim $\pdim\K[\Delta_G]=n-1$. For if not,  assume  $\pdim\K[\Delta_G]=n$. Then the Auslander-Buchsbaum formula implies that $\dep\K[\Delta_G]=0$. Note that the maximal ideal $\displaystyle\mm$ is an associated prime of $\K[\Delta_G]$  if and only if $\dep\K[\Delta_G]=0$. It follows that $\bight I(G)=n$ which is a contradiction. Hence $\pdim\K[\Delta_G]=\max_{1\leq i \leq n}\{\deg_{G}(x_i)\}=n-1$.
\end{proof}
\begin{comment}
\begin{figure}[ht]
	\begin{center}
		\begin{tikzpicture}[x = 2cm, y = 1.5cm]
			\draw[fill] (0,0) circle [radius = 0.04];
			\draw[fill] (1,0) circle [radius = 0.04];
			\draw[fill] (1.3,.8) circle [radius = 0.04];
			\draw[fill] (.5,1.5) circle [radius = 0.04];
			\draw[fill] (-.3,.8) circle [radius = 0.04];
			\draw[fill] (.5,.7) circle [radius = 0.04];
			
			\draw (0,0)--(1,0)--(1.3,.8)--(.5,1.5)--(-.3,.8)--(0,0);
			\draw (0,0)--(.5,.7);
			\draw (1,0)--(.5,.7);
			\draw (1.3,.8)--(.5,.7);
			\draw (.5,1.5)--(.5,.7);
			\draw (-.3,.8)--(.5,.7);
			
			\node[below=.1] at (.5,.7) {$x$};
		\end{tikzpicture}
		\caption{}\label{fig10}
	\end{center}
\end{figure}
\end{comment}
\begin{example}
Here we consider some graphs with a full-vertex. 
	\begin{itemize}
		\item We have $\pdim\K[\Delta_{\mathcal{K}_n}]=n-1$ since each vertex $x\in V(\mathcal{K}_n)$ is a full-vertex.
		\item The \emph{wheel} graph $W_{n}$ is a graph obtained by connecting a vertex $x$ to all vertices of an induced cycle with $n-1$ vertices, see $W_5$ in Figure \ref{fig4}. Hence $\pdim\K[\Delta_{W_{n}}]=n-1$.
		\item A \emph{star complete}   graph  is obtained by attaching  complete graphs  to a vertex $x$, in each case we attach all the vertices  of the complete graphs to $x$. For example, a bowtie graph is  star complete graph since it is obtained by attaching two copies of $\mathcal{K}_2$ to a vertex.  Then the projective dimension of a star complete graph with $n$ vertices is $n-1$.
		\begin{figure}[ht]
				\begin{center}
					\begin{tikzpicture}[x = 2cm, y = 1.5cm]
						\draw[fill] (0,0) circle [radius = 0.04];
						\draw[fill] (1,0) circle [radius = 0.04];
						\draw[fill] (1.3,.8) circle [radius = 0.04];
						\draw[fill] (.5,1.5) circle [radius = 0.04];
						\draw[fill] (-.3,.8) circle [radius = 0.04];
						\draw[fill] (.5,.7) circle [radius = 0.04];
						\draw[fill] (1.8,0) circle [radius = 0.04];
						
						\draw (0,0)--(.5,.7)--(-.3,.8)--(0,0);
						\draw (1,0)--(.5,.7)--(1.3,.8)--(1.8,0)--(1,0);
						\draw (1.3,.8)--(1,0);
						\draw (.5,1.5)--(.5,.7);
						\draw (1.8,0)--(.5,.7);
					\end{tikzpicture}
					\caption*{A star complete graph}\label{fig10}
				\end{center}
		\end{figure}
	\end{itemize}
\end{example}

\begin{remark}
	Let $n\geq6$. Note that $W_n$ is not a co-chordal graph. Hence  $\K[\Delta_{W_n}]$ does not have a 2-linear resolution but   $\pdim\K[\Delta_{W_n}]=\max_{1\leq i \leq n}\{\deg_{W_n}(x_i)\}$.
\end{remark}

The class of $d$-tree and generalized $d$-tree graphs  are initially  defined by Fr\"oberg in  \cite{Froberg1990}. In fact generalized $d$-tree graphs are exactly the chordal graphs. Here we define a new class of graphs which  lie strictly between the $d$-trees and chordal graphs. 
\begin{definition}\label{d-tree definition}
	Let $(d_1,d_2,\dots,d_q)$ be a non-increasing sequence of positive integers. Then a \emph{$(d_1,d_2,\dots,d_q)$-tree} is a graph $G$ constructed inductively  as follows:
	\begin{enumerate}
		\item[i)] The graph $H_1=\mathcal{K}_{d_1}$,
		\item[ii)] $H_i=H_{i-1}\bigcup_{\mathcal{K}_{d_i-1}}\mathcal{K}_{d_i}$ for $2\leq i\leq q$, and
		\item[iii)] $G=H_q$.
	\end{enumerate}
\end{definition}
The clique complex of a $(d_1,d_2,\dots,d_q)$-tree is $\Delta(G)=\lr{F_1,\dots,F_q}$ where $F_i=V(\mathcal{K}_{d_i})$ for $1\leq i\leq q$. Form the construction of $(d_1,d_2,\dots,d_q)$-tree we observe that a $d$-tree is $(d_1,d_2,\dots,d_q)$-tree with $d_i=d$ for $1\leq i\leq q$. Also $(d_1,d_2,\dots,d_q)$-tree is a chordal graph.  That is, we have the following implications.
\begin{center}
	$d\mbox{-tree graphs}\Rightarrow(d_1,d_2,\dots,d_q)\mbox{-tree graphs}\Rightarrow\mbox{chordal graphs}$.
\end{center}
However the converse of implications do not hold in general, for example see Figure \ref{fig2}.
\begin{figure}[ht]
	\begin{subfigure}{.45\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (1,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (2,1) circle [radius = 0.04];
				
				\draw (0,0)--(1,1)--(1,0)--(0,0);
				\draw (1,0)--(1,1)--(2,1)--(1,0);
				
			\end{tikzpicture}
			\caption*{A $(3,3)$-tree}
		\end{center}
	\end{subfigure}
	\begin{subfigure}{.5\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (.5,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (2,0) circle [radius = 0.04];
				
				\draw (0,0)--(.5,1)--(1,0)--(0,0);
				\draw (1,0)--(2,0);
				
			\end{tikzpicture}
			\caption*{A $(3,2)$-tree but not $d$-tree.}
		\end{center}
	\end{subfigure}
	
	\begin{subfigure}{1\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (.5,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (2,0) circle [radius = 0.04];
				\draw[fill] (1.5,1) circle [radius = 0.04];
				
				\draw (0,0)--(.5,1)--(1,0)--(0,0);
				\draw (1,0)--(1.5,1)--(2,0)--(1,0);
				
			\end{tikzpicture}
			\caption*{A chordal graph that is  not a $(d_1,d_2,\dots,d_q)$-tree.}
		\end{center}
	\end{subfigure}
\caption{}\label{fig2}
\end{figure}



Note that for any sequence $(d_1,d_2,\dots,d_q)$ in the definition \ref{d-tree definition}, there is at least one $(d_1,d_2,\dots,d_q)$-tree. Indeed, we can have two non-isomorphic  $(d_1,d_2,\dots,d_q)$-trees in general,  see Figure \ref{fig5}.
\begin{figure}[ht]
	\begin{subfigure}{.55\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (1,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (2,1) circle [radius = 0.04];
				\draw[fill] (3,1) circle [radius = 0.04];
				
				\draw (0,0)--(1,1)--(1,0)--(0,0);
				\draw (1,0)--(1,1)--(2,1)--(1,0);
				\draw (2,1)--(3,1);
				
			\end{tikzpicture}
		\end{center}
	\end{subfigure}
	\begin{subfigure}{.35\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (1,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (2,1) circle [radius = 0.04];
				\draw[fill] (2,0) circle [radius = 0.04];
				
				\draw (0,0)--(1,1)--(1,0)--(0,0);
				\draw (1,0)--(1,1)--(2,1)--(1,0);
				\draw (1,0)--(2,0);
				
			\end{tikzpicture}
		\end{center}
	\end{subfigure}
	\caption{Two non-isomorphic  $(3,3,2)$-tree graphs.}\label{fig5}
\end{figure}


 Faridi \cite{Faridi2003} introduced the notion of a leaf for a simplicial complex $\Delta$ as follows, a facet $F$ of $\Delta$ is called \emph{leaf}  if there is  a facet $M$ of $\Delta$ with $F\neq M$ such that $N\cap F\subset M\cap F$ for all facet $N$ of $\Delta$ with $N\neq F$. 
 Then Zheng \cite{Zheng2004} defined the concept of {quasi-forest}. 
 A simplicial complex $\Delta$ is   \emph{quasi-forest} if there is  an order $F_1,\ldots, F_r$ of the facets of $\Delta$, called a \emph{leaf order}, such that $F_i$ is a leaf of the simplicial complex $\langle F_1,\ldots, F_i\rangle$ for each $i=1,\ldots, r$.
A \emph{free vertex} is a vertex which belongs to exactly one facet. Bj\"orner and Wachs extended the definitions of vertex decomposability and shellability for non-pure cases, see {\cite[Definition 2.1]{BjornerWachs1996}} and {\cite[Definition 11.1]{BjornerWachs1997}}. A simplicial complex $\Delta$ is  \emph{vertex decomposable} if $\Delta$ is an empty set, $\Delta$ is a simplex or there exists a vertex $v \in V$ such that
\begin{enumerate}
	\item[i)]  $\del_{\Delta}(v)$ and $\link_{\Delta}(v)$ are both vertex decomposable.
	\item[ii)]\label{shedding} No facet $F$ of $\link_{\Delta}(v)$ is also a facet of $\del_{\Delta}(v)$ (equivalently, every facet of $\del_\Delta(v)$ is a facet of $\Delta$). 
\end{enumerate}
If $\Delta$ is pure, we call $\Delta$ {pure vertex decomposable}. A vertex $v$ that satisfies condition (ii) is called \emph{shedding vertex}. A simplicial complex $\Delta$ is \emph{shellable}  if the facets of $\Delta$ can be ordered, say $F_1,\ldots,F_r$, such that for all $1\leq i<j\leq r$, there  exists some $v\in F_j\setminus F_i$ and some $1\leq k<j$ with $F_j\setminus F_k= \{v\}$. Such ordering  $F_1,\ldots,F_r$  is called a \emph{shelling order}. If $\Delta$ is pure, we call $\Delta$ {pure shellable}. Bj\"orner and Wachs showed that if $\Delta$ is a vertex decomposable, then $\Delta$ is shellable {\cite[Theorem 11.3]{BjornerWachs1997}. Stanley showed that if $\Delta$ is shellable, then $\Delta$ is sequentially Cohen-Macaulay {\cite[p.87]{Stanley1996}}. Hence, if $\Delta$ is vertex decomposable, then $\Delta$ is sequentially Cohen-Macaulay. Dirac's theorem \cite{Dirac1961} on chordal graphs says that $\Delta_G$ is quasi-forest if and only if $G$ is co-chordal. Hence by {\cite[Theorem 1]{Froberg1990}}, $\Delta_G$ is quasi-forest if and only if $\K[\Delta_G]$ has 2-linear resolution.
	
	\begin{theorem}\label{d-tree VD}
		Let $G$ be a graph such that $\overline{G}$ is a $(d_1,d_2,\dots,d_q)$-tree. Then $\Delta_G$ is vertex decomposable quasi-forest (hence shellable and sequentially Cohen-Macaulay).	
	\end{theorem}
	\begin{proof}
		For $i=1,\dots,q$, let $F_i=V(\mathcal{K}_{d_i})$. Then form the definition of $(d_1,d_2,\dots,d_q)$-tree the complex $\Delta_G=\lr{F_1,F_2,\dots,F_q}$ is the clique complex of $\overline{G}$. By Dirac's theorem, see \cite[Theorem 1 and 2]{Dirac1961},  the graph $\overline{G}$ is chordal. Hence $\Delta_G$ is quasi-forest. \\ For the rest of the proof we use induction on $|V(G)|$ to show that $\Delta_G$ is vertex decomposable. If $|V(G)|=2$, then $G$ is an edge. Clearly $\overline{G}$ is $(1,1)$-tree and $\Delta_G$ is vertex decomposable. Suppose $|V(G)|=n>2$ for some integer $n$ and the statement is true for any graph with less than $n$ vertices. By definition of $(d_1,d_2,\dots,d_q)$-tree, there is a vertex $x\in F_q\backslash\bigcup_{i=1}^{q-1}F_i$ and $F_q\backslash F_j=\{x\}$ for some $1\leq j<q-1$. Hence $x$ is a shedding vertex. 
Then $\del_{\Delta_G}(x)=\lr{F_1,\dots,F_{q-1}}$ and $\link_{\Delta_G}(x)=\lr{F_q\backslash\{x\}}$. 
 Note that $\overline{G}\backslash x$ is a $(d_1,\dots,d_{q-1})$-tree and $\overline{G}\backslash N_{\overline{G}}[x]$ is $(d_{q}-1)$-tree. On the other hand $\del_{\Delta_G}(x)=\Delta_{G\backslash x}$ and  $\link_{\Delta_G}(x)=\Delta_{G\backslash N_G[x]}$. Hence by induction hypothesis $\del_{\Delta_G}(x)$ and $\link_{\Delta_G}(x)$ are vertex decomposable. Therefore $\Delta_G$ is vertex decomposable.
	\end{proof}
	
	\begin{remark}\label{remark 2}
		Let  $\Delta_G=\lr{F_1,\dots, F_q}$ be the independence complex of a graph $G$ such that $\overline{G}$ is a $(d_1,\dots, d_q)$-tree. Then from the definition of shelling and leaf order we note that $F_1,\dots, F_q$ is a shelling and a leaf order of $\Delta_G$.
	\end{remark}
	





	
The following Corollary follows immediately form Theorem \ref{d-tree VD} and {\cite[Lemma 3.6]{FranciscoTuyl2007}}.
	
	\begin{corollary}
		The clique complex of a $d$-tree is pure vertex decomposable (hence pure shellable {\cite[Theorem 2.13]{MoradiKiani2010}} and Cohen-Macaulay {\cite[Theorem 2]{Froberg1990}}).
	\end{corollary}
	 In the following we provide some necessary conditions for a graph to be a $(d_1,d_2,\dots,d_q)$-tree. 

	\begin{proposition}\label{qf b shedding}
		Let $G$ be a graph such that $\overline{G}$ is a $(d_1,d_2,\dots,d_q)$-tree. Then any vertex of maximum degree in $G$ is a free and shedding vertex of $\Delta_G$.
	\end{proposition}
	%
	%

		\begin{proof}
 For $i=1, \ldots, q$, let $F_{i}=V\left(\mathcal{K}_{d_{i}}\right)$. Then form the definition of $\left(d_{1}, d_{2}, \ldots, d_{q}\right)$-tree the complex $\Delta_{G}=\left\langle F_{1}, F_{2}, \ldots, F_{q}\right\rangle$ is the independence complex of $G$. Let $x$ be a vertex  of  the maximum degree in $G$. Then degree of $x$ is minimum  in $\overline{G}$. 
 But since $F_{q}$ contains a free vertex and it is of minimum cardinality in $\Delta_{G}$ we have $\left|F_{j}\right|=\left|F_{q}\right|$ whenever $x \in F_{j}$, for $1 \leq j \leq q$. Thus $x$ is a free vertex, otherwise degree of $x$ cannot be minimum in $\overline{G}$.
To show $x$ is a shedding vertex we start by considering the case when $x \in F_{1}$. Then we have $|F_{1}|=|F_j|$ for all $j$. Suppose that $x$ is not shedding.  Then $F_1\backslash\{x\}$ is not a face of  $\left\langle  F_{2}, \ldots, F_{q}\right\rangle$. Hence $\mathcal{K}_{d_{2}}$ is attached to $\mathcal{K}_{d_{1}}$ from at most $\mathcal{K}_{d_{2}-2}$, that is $\overline{G}$ is not a $\left(d_{1}, d_{2}, \ldots, d_{q}\right)$-tree which is a contradiction. Now, if $x \in F_{j}$ for some $2 \leq j \leq q$, then there is $1 \leq i<j$ such that $F_{j} \backslash F_{i}=\{x\}$. Hence in all cases $x$ is a shedding vertex.
	\end{proof}

	%
	%
	%
	%
	\begin{comment}
	
	\begin{proof}
		Let $\Delta_G=\lr{F_1,\dots,F_q}$ be the independence complex of $G$ such that $d_i=|F_i|$ for $1\leq i\leq q$. By definition of $(d_1,d_2,\dots,d_q)$-tree there is a free vertex $x\in F_q$. Hence $x$ is of a maximum degree in $G$ which is a free vertex of $\Delta_G$. By Remark \ref{remark 2} $F_1,\dots,F_q$ is a shelling order of $\Delta_G$. Then for all $1\leq i<q$, there  exists some $x\in F_q\setminus F_i$ and some $1\leq j<q$ with $F_q\setminus F_j= \{x\}$. Thus $F_q\backslash\{x\}\subset F_j$. Therefore $x$ is a shedding vertex.
	\end{proof}
	The converse of Lemma \ref{qf b shedding} may not be true. Let $\Delta_G=\lr{x_1x_2x_3x_4,x_2x_3x_4x_5,x_4x_5x_6}$. Then $\overline{G}$ is a $(4,4,3)$-tree. The vertex $x_1$ is a free and shedding vertex of $\Delta_G$ but $\deg_{G}(x_1)=2$ is not maximum. 
	\end{comment}
	
	
		
	\begin{proposition}\label{qf max adjacent}
		If $G$ is a graph such that $\overline{G}$ is a $(d_1,d_2,\dots,d_q)$-tree, then any two vertices of $G$ with maximum degree are adjacent.
	\end{proposition}
	\begin{proof}
	Suppose that $G$ has two non-adjacent vertices $x$ and $x'$ of maximum degree. Then we show that $N_G(x)=N_G(x')$. 
		 Assume there is  $v'\in N_G(x')\backslash N_G(x)$. Then $d(x,x')\geq2$ and $d(x,v')\geq2$. Hence $G\backslash N_G[x]$ contains at least the edge $\{x',v'\}$. Hence $x$ is not a free vertex in $\Delta_G$, this contradicts Proposition \ref{qf b shedding}. Therefore $N_G(x)=N_G(x')$. Then  any facet $F\in\Delta_G$ containing $x$ must also contain $x'$. Hence $F\backslash\{x\}$ is a facet of $\del_{\Delta_G}(x)$. Thus $x$ is not a shedding vertex, again this contradicts Proposition \ref{qf b shedding}.
	\end{proof}
	
	\begin{example}
		Consider the following applications of  Propositions~\ref{qf b shedding} and \ref{qf max adjacent}. 
		\begin{itemize}
		\item Let $G$ be the complement of the graph in  Figure \ref{fig6}. The degree of $x$ is maximum  in $G$ but $x$ is not a free vertex in $\Delta_G$. Hence $\overline{G}$ is not a $(d_1,d_2,\dots,d_q)$-tree.
			\item The complement of $C_4$ is not a $(d_1,d_2,\dots,d_q)$-tree since it has  non-adjacent vertices of maximum degrees.
			\item The complement of the graph $G$ in Example \ref{example 3} is not $(d_1,d_2,\dots,d_q)$-tree since $x_2$ and $x_4$ are non-adjacent maximum degrees of $G$.
		\end{itemize}
		\begin{figure}[ht]
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
			
			
				
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (.5,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (2,0) circle [radius = 0.04];
				\draw[fill] (3,0) circle [radius = 0.04];
				\draw[fill] (3.5,1) circle [radius = 0.04];
				\draw[fill] (4,0) circle [radius = 0.04];
				
				\draw (0,0)--(.5,1)--(1,0)--(0,0);
				\draw (1,0)--(2,0);
				\draw (2,0)--(3,0);
				\draw (3,0)--(3.5,1)--(4,0)--(3,0);
				
			
			
			
				\node[above] at (2,0) {$x$};
			
			
			
			\end{tikzpicture}
		\end{center}
		\caption{}\label{fig6}
	\end{figure}
	\end{example}
	
	In the following result we provide a sufficient  condition for which   the  Eliahou and Villarreal conjecture is true. To our knowledge the given condition together with Theorem~\ref{pdim G1 empty} generalise all the existing classes of graphs for which the conjecture holds. 	\begin{theorem}\label{d-tree pdim}
		Let $G$ be a connected graph such that $\overline{G}$ is a $(d_1,d_2,\dots,d_q)$-tree. Then $\pdim\K[\Delta_G]=\displaystyle\max_{1\leq i \leq n}\{\deg_G(x_i)\}$.
	\end{theorem}
	\begin{proof}
		For $i=1,\dots,q$, let $F_i=V(\mathcal{K}_{d_i})$. Then $\Delta_G=\lr{F_1,F_2,\dots,F_q}$ is the clique complex of $\overline{G}$. By the definition of $(d_1,d_2,\dots,d_q)$-tree there is a free vertex $x$ in $F_q$ and $\bight I(G)=n-|F_q|$. Note that $ \max_{1\leq i \leq n}\{\deg_G(x_i)\}=\deg_{G}(x)$ since $x$ is a free vertex of $F_q$ and $F_q$ is of minimum cardinality. Let $F_q=\{x,v_2,\dots,v_r\}$. By Lemmas \ref{max ind} and $\ref{max-process}$, $\bight I(G)=n-|F_q|=|N_G[F_q]|-|F_q|=|N_G(F_q)|=\deg_{G}(x)+\sum_{i=2}^{r}\deg_{G_{i}}(v_i)$. We have $G\backslash N_G[x]$ is a set of isolated vertices since $x$ is a free vertex in $\Delta_G$. Hence $\sum_{i=2}^{r}\deg_{G_{i-1}}(v_i)=0$. Thus $\bight I(G)=\deg_{G}(x)$. Theorem \ref{d-tree VD} and \cite[Corollary 3.33]{MoreyVillarreal2012} imply that $\pdim\K[\Delta_G]=\bight I(G)=\deg_{G}(x)$.
	\end{proof}

\begin{remark}
	Note that if $G$ is the complement of a $(d_1,d_2,\dots,d_q)$-tree. Then by Auslander-Buchsbaum formula and Theorem \ref{d-tree pdim} we have $\dep\K[\Delta_G]=d_q$.
\end{remark}

\begin{example}\label{example 2}
	Consider the graphs $G_1$ and $G_2$ in Figure \ref{fig3}. Then $\overline{G}_1$ is $(2,2,1)$-tree and $\overline{G}_2$ is $(4,3,3,3,3)$-tree. Hence $\dep\K[\Delta_{G_1}]=1$, $\pdim\K[\Delta_{G_1}]=3$, $\dep\K[\Delta_{G_2})]=3$ and $\pdim\K[\Delta_{G_2})]=5$.
	\begin{figure}[ht]
		\begin{subfigure}{.45\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0,0) circle [radius = 0.04];
					\draw[fill] (.5,1) circle [radius = 0.04];
					\draw[fill] (1,0) circle [radius = 0.04];
					\draw[fill] (2,0) circle [radius = 0.04];
					
					\draw (0,0)--(.5,1)--(1,0)--(0,0);
					\draw (1,0)--(2,0);
				\end{tikzpicture}
				\caption*{The graph $G_1$.}
			\end{center}
		\end{subfigure}
		\begin{subfigure}{.45\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0,0) circle [radius = 0.04];
					\draw[fill] (.7,0) circle [radius = 0.04];
					\draw[fill] (.7,.7) circle [radius = 0.04];
					\draw[fill] (0,.7) circle [radius = 0.04];
					\draw[fill] (1.25,.35) circle [radius = 0.04];
					\draw[fill] (-.55,.35) circle [radius = 0.04];
					\draw[fill] (.35,-.7) circle [radius = 0.04];
					\draw[fill] (.35,1.4) circle [radius = 0.04];
					
					\draw (0,0)--(.7,0)--(.7,.7)--(0,.7)--(0,0);
					\draw (.7,0)--(1.25,.35)--(.7,.7)--(.7,0);
					\draw (0,0)--(-.55,.35)--(0,.7)--(0,0);
					\draw (0,.7)--(.35,1.4)--(.7,.7)--(.7,0);
					\draw (0,0)--(.35,-.7)--(.7,0)--(0,0);
					\draw (0,0)--(.7,.7);
					\draw (0,.7)--(.7,0);
				\end{tikzpicture}
				\caption*{The graph $G_2$.}
			\end{center}
		\end{subfigure}
		\caption{}\label{fig3}
	\end{figure}
\end{example}

The converse of Theorem \ref{d-tree pdim} need not hold in general. In order to see this, let $G$ be the graph in Figure \ref{fig4}.
\begin{figure}[ht]
	\begin{subfigure}{.45\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (0,1) circle [radius = 0.04];
				\draw[fill] (1,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (.5,.5) circle [radius = 0.04];
				
				\draw (0,0)--(0,1)--(1,1)--(1,0)--(0,0);
				\draw (.5,.5)--(1,1)--(.5,.5)--(1,0);
				\draw (0,1)--(.5,.5);
				\draw (.5,.5)--(0,0);
				
			
			
			
			
				\node[below=.05] at (.5,.5) {$x$};
			\end{tikzpicture}
			\caption*{The graph $G$.}
		\end{center}
	\end{subfigure}
	\begin{subfigure}{.4\textwidth}
		\begin{center}
			\begin{tikzpicture}[x = 2cm, y = 1.5cm]
				\draw[fill] (0,0) circle [radius = 0.04];
				\draw[fill] (0,1) circle [radius = 0.04];
				\draw[fill] (1,0) circle [radius = 0.04];
				\draw[fill] (1,1) circle [radius = 0.04];
				\draw[fill] (.5,.5) circle [radius = 0.04];
				
				\draw (0,0)--(0,1);
				\draw (1,0)--(1,1);
			
			
			
			
			
				\node[below] at (.5,.5) {$x$};
			\end{tikzpicture}
			\caption*{The graph of $\overline{G}$.}
		\end{center}
	\end{subfigure}
	\caption{}\label{fig4}
\end{figure}
	By Theorem \ref{pdim G1 empty} $\pdim\K[\Delta_G]= \max_{1\leq i \leq 5}\{\deg_G(x_i)\}=4$ since $x$ is a full-vertex of $G$. But $\overline{G}$ is not a $(d_1,d_2,\dots,d_q)$-tree.
	
	In  \cite[Theorem 2.13]{MoradiKiani2010},  Moradi and Kiani proved that 
	the projective dimension of $\K[\Delta_G]$ is equal to the maximum degree of vertices of $G$ whenever $\overline{G}$ is a $d$-tree. In the next corollary we show that Moradi and Kiani's result is a consequence of Theorem \ref{d-tree pdim}.
	
	\begin{corollary}[{\cite[Theorem 2.13]{MoradiKiani2010}}]
		Let $G$ be a graph such that $\overline{G}$ is a $d$-tree. Then $\pdim\K[\Delta_G]=\max_{1\leq i \leq n}\left\{\deg_{G}(x_i)\right\}$.
	\end{corollary}
	\begin{proof}
		Any $d$-tree graph is an unmixed $(d_1,d_2,\dots,d_q)$-tree. The graph $G$ is connected since $\overline{G}$ is $d$-tree. Then the result follows form Theorem \ref{d-tree pdim}.
	\end{proof}
	\sloppy For integers  $m\geq1$ and  $r\geq0$, the graph $G_{m,r}$ is  obtained by attaching $r$ edges at each vertex of $\mathcal{K}_m$. Gitler and Valencia in \cite{GitlerValencia2005} show that $\pdim\K[\Delta_{G_{m,r}}]=\max_{1\leq i \leq n}\{\deg_{G_{m,r}}(x_i)\}$ where $n=m(r+1)$.   Theorem \ref{d-tree pdim} generalises their result, since the complement of $G_{m,r}$ is $(mr, \underbrace{(m-1)r+1,(m-1)r+1,\dots,(m-1)r+1}_{m\textup{-times}})$-tree. 
	
	\begin{corollary}
		[{\cite[Proposition 4.9 and Proposition 4.12]{GitlerValencia2005}}]
		Let $G=G_{m,r}$ or let $G=G_{m,i_1,\dots,i_m}$ be the graph obtained by attaching $i_j$ edges at each vertex $x_j$ of $\mathcal{K}_m$ such that $i_j\leq i_{j+1}$ for all $j$. Then $\pdim\K[\Delta_G]=\displaystyle\max_{1\leq i \leq n}\{\deg_{G}(x_i)\}$.
	\end{corollary}



	%
	
	A \emph{separating set} in a connected graph $G$ is a set of edges whose deletion turns $G$ into a disconnected graph. If $G$ is connected and not a complete graph, its \emph{edge connectivity} $\lambda(G)$ is the size of the smallest separating set in $G$. A graph $G$ is $k$-connected if $\lambda(G)\geq k$.
	
	\begin{lemma}\label{k-connected}
		 For $q\geq2$, let $G$ be a connected $(d_1,d_2,\dots,d_q)$-tree. Then $G$ is $d_q-1$-connected.
	\end{lemma}
	\begin{proof}
		Let $x$ be the free vertex in  the facet $F_q=V(\mathcal{K}_{d_q})$ of $\Delta(G)$. Then $\lambda(G)=d_q-1$ since $F_q$ has the minimum cardinality and $G$ is a chordal graph. Therefore $G$ is $d_q-1$-connected. 
	\end{proof}
	
	\begin{example}
		Consider the graphs $G_1$ and $G_2$ in Figure \ref{fig11}. Then $G_1$ is a $(3,2)$-tree and $G_2$ is a $(3,3)$-tree. Hence by Lemma \ref{k-connected}, $G_1$ is 1-connected and $G_2$ is 2-connected.
	\begin{figure}[ht]
		\begin{subfigure}{.45\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0,0) circle [radius = 0.04];
					\draw[fill] (.5,1) circle [radius = 0.04];
					\draw[fill] (1,0) circle [radius = 0.04];
					\draw[fill] (2,0) circle [radius = 0.04];
					
					\draw (0,0)--(.5,1)--(1,0)--(0,0);
					\draw (1,0)--(2,0);
				\end{tikzpicture}
				\caption*{The graph $G_1$.}
			\end{center}
		\end{subfigure}
		\begin{subfigure}{.45\textwidth}
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0,0) circle [radius = 0.04];
					\draw[fill] (1,1) circle [radius = 0.04];
					\draw[fill] (1,0) circle [radius = 0.04];
					\draw[fill] (2,1) circle [radius = 0.04];
					
					\draw (0,0)--(1,1)--(1,0)--(0,0);
					\draw (1,0)--(1,1)--(2,1)--(1,0);
				\end{tikzpicture}
				\caption*{The graph $G_2$.}
			\end{center}
		\end{subfigure}
		\caption{}\label{fig11}
	\end{figure}
\end{example}
	
	Let $\Delta_G$ be a quasi-forest  simplicial complex. If $G$ is disconnected, then it is a union of totally disconnected graph with a connected component. 
	Hence, after dropping the connectedness assumption in Theorem \ref{d-tree pdim} our formula for computing the projective dimension becomes \begin{equation*}
		\pdim\K[\Delta_G]=\displaystyle\max_{1\leq i \leq n}\{\deg_{G}(x_i)\}+\text{number of isolated vertices}.
	\end{equation*}
	For example consider the following graph $G$ in Figure \ref{fig9}. Let $G^\prime$ be the connected component of $G$. By Theorem \ref{d-tree pdim} we have $\pdim\K[\Delta_{G^\prime}]=3$ since $\overline{G^\prime}$ is a $(2,1,1)$-tree. Hence $\pdim\K[\Delta_G]=3+1=4$.
	\begin{figure}[ht]
			\begin{center}
				\begin{tikzpicture}[x = 2cm, y = 1.5cm]
					\draw[fill] (0,0) circle [radius = 0.04];
					\draw[fill] (1,1) circle [radius = 0.04];
					\draw[fill] (1,0) circle [radius = 0.04];
					\draw[fill] (0,1) circle [radius = 0.04];
					\draw[fill] (2,0) circle [radius = 0.04];
					
					\draw (0,0)--(1,0)--(1,1)--(0,1)--(0,0);
					\draw (1,0)--(0,1);
					
				
				
				
				
					\node[above] at (2,0) {$x$};
				\end{tikzpicture}
			\end{center}
		\caption{The graph $G$.}\label{fig9}
	\end{figure}
	
	
	\section{Some questions}
	In this section we propose some questions which may naturally arise after looking at the results of this paper.
	\begin{question}\label{question 1}
	Is there a graph $G$ that is not a member of the following classes  of graphs:
 \begin{enumerate}
 \item[i)] class of graphs with a full vertex, 
 \item[ii)] class of graphs whose complement is a $(d_1,d_2,\dots,d_q)$-tree for some non-increasing sequence of integers $(d_1,d_2,\dots,d_q)$.
 \end{enumerate}
	but  $\pdim\K[\Delta_G]=\displaystyle\max_{1\leq i \leq n}\left\{\deg_{G}(x_i)\right\}$?
\end{question}
The answer of Question \ref{question 1} is positive. For example, let $G$ be a graph as Figure \ref{fig7}. Then $\pdim\K[\Delta_G]=\deg_{G}(x)=3$ but $G$ does not have a full vertex or it is not the complement of a $(d_1,d_2,\dots,d_q)$-tree.
\begin{figure}[ht]
	\begin{center}
		\begin{tikzpicture}[x = 2cm, y = 1.5cm]
			\draw[fill] (0,0) circle [radius = 0.04];
			\draw[fill] (1,0) circle [radius = 0.04];
			\draw[fill] (2,0) circle [radius = 0.04];
			\draw[fill] (2,1) circle [radius = 0.04];
			\draw[fill] (3,0) circle [radius = 0.04];
			\draw[fill] (4,0) circle [radius = 0.04];
			
			\draw (0,0)--(1,0);
			\draw (1,0)--(2,0);
			\draw (2,0)--(3,0);
			\draw (2,0)--(2,1);
			\draw (3,0)--(4,0);
			
		
		
			\node[below] at (2,0) {$x$};
		
		
		
		\end{tikzpicture}
		\caption{The graph $G$.}\label{fig7}
	\end{center}
\end{figure}
\\In Theorem~\ref{pdim max} we showed that for any graph $G$ we have  $\bight I(G)\geq\max_{1\leq i \leq n}\{\deg_G(x_i)\}$, it may be reasonable to consider the following questions.
\begin{question}\label{big=max}
For which class of graphs $\mathcal{C}(G)$ we have $\displaystyle\bight I(G)=\max_{1\leq i \leq n}\{\deg_G(x_i)\}$?
  \end{question}

\begin{question}\label{prob2}
	Let $k$ be a positive integer, for which class of graphs $\mathcal{C}(G)$ we have $\displaystyle\pdim\K[\Delta_G]=\max_{1\leq i \leq n}\{\deg_G(x_i)\}+k$?
\end{question}

Regarding the Questions~\ref{big=max} and \ref{prob2},  we have $\bight I(C_4)=\max_{1\leq i \leq 4}\deg_{C_4}(x_i)=2$ and $\pdim\K[\Delta_{C_4}]=\max_{1\leq i \leq 4}\deg_{C_4}(x_i)+1=3$.

\begin{comment}
\begin{conjecture}\label{conjecture 1}
	Let $\Delta$ be a vertex decomposable quasi-forest simplicial complex. Then $\Delta$ has a facet of minimum  cardinality that contains a free and shedding vertex.
	\end{conjecture}
\end{comment}
A positive answer to the following question with Theorem \ref{d-tree VD} characterise  the vertex decomposable quasi-forest simplicial complexes in terms of   $(d_1,d_2,\dots,d_q)$-trees.
\begin{question}\label{qf shellable d-tree}
	A simplicial complex $\Delta_G$ is vertex decomposable quasi-forest, then is there a non-increasing sequence of positive integers $(d_1,d_2,\dots,d_q)$ such that $\overline{G}$ is a $(d_1,d_2,\dots,d_q)$-tree?
\end{question}

\bibliographystyle{plain}
