% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf On well-covered, vertex decomposable and Cohen-Macaulay graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Iv\'an D. Castrill\'on\thanks{Partially supported by CONACYT and ABACUS-CINVESTAV.}\\
\small Departamento de Matem\'aticas\\[-0.8ex]
\small Centro de Investigaci\'on y de Estudios Avanzados del IPN \\[-0.8ex] 
\small Ciudad de M\'exico, M\'exico\\
\small\tt idcastrillon@math.cinvestav.mx\\
\and
Roberto Cruz\\
\small Instituto de Matem\'aticas\\[-0.8ex]
\small Universidad de Antioquia\\[-0.8ex]
\small Medell\'in, Colombia\\
\small\tt roberto.cruz@udea.edu.co\\
\and
Enrique Reyes\\
\small Departamento de Matem\'aticas\\[-0.8ex]
\small Centro de Investigaci\'on y de Estudios Avanzados del IPN \\[-0.8ex] 
\small Ciudad de M\'exico, M\'exico\\
\small\tt ereyes@math.cinvestav.mx\\}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jan 17, 2016}{2016}\\
\small Mathematics Subject Classifications: 13F55, 05E40, 05E45, 05C75}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  Let $G=(V,E)$ be a graph. If $G$ is a K$\ddot{{\rm o}}$nig graph or if $G$ is a graph without 3-cycles and 5-cycles, we prove that the following conditions are equivalent: $\Delta_{G}$ is pure shellable, $R/I_{\Delta}$ is Cohen-Macaulay, $G$ is an unmixed vertex decomposable graph and $G$ is well-covered with a perfect matching of K$\ddot{{\rm o}}$nig type $e_{1},...,e_{g}$ without 4-cycles with two $e_i$'s. Furthermore, we study vertex decomposable and shellable (non-pure) properties in graphs with\-out 3-cycles and 5-cycles. Finally, we give some properties and relations between cri\-ti\-cal, extendable and shedding vertices.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Cohen-Macaulay, shellable, well-covered, unmixed, vertex decompo\-sable, K$\ddot{{\rm o}}$nig, girth
\end{abstract}

\section{Introduction}

Let $G$ be a simple graph (without loops and multiplies edges) whose vertex set is $V(G)=\{x_{1},...,x_{n}\}$ and edge set $E(G)$. Let $R=k[x_{1},...,x_{n}]$ be a polynomial ring over a field $k$. The \textit{edge ideal} of $G$, denoted by $I(G)$, is the ideal of $R$ generated by all monomials $x_{i}x_{j}$ such that $\{x_{i},x_{j}\}\in E(G)$. $G$ is a \textit{Cohen-Macaulay graph} if $R/I(G)$ is a Cohen-Macaulay ring (see \cite{BH}, \cite{Villa}). A subset $F$ of $V(G)$ is a \textit{stable set} or \textit{independent set} if $e\nsubseteq F$ for each $e\in E(G)$. The cardinality of the maximum stable set is denoted by $\beta (G)$. $G$ is called \textit{well-covered} if every maximal stable set has the same cardinality. On the other hand, a subset $D$ of $V(G)$ is a \textit{vertex cover} of $G$ if $D\cap e \neq \emptyset$ for every $e\in E(G)$. The number of vertices in a minimum vertex cover of $G$ is called the \textit{covering} \textit{number} of $G$ and it is denoted by $\tau (G)$. This number coincide with ht$(I(G))$, the \textit{height} of $I(G)$. If the minimal vertex covers have the same cardinality, then $G$ is called an \textit{unmixed} graph. Notice that, $D$ is a vertex cover if and only if $V(G)\setminus D$ is a stable set. Hence, $\tau(G)=n-\beta(G)$ and $G$ is well-covered if and only if $G$ is unmixed. The \textit{Stanley-Reisner} \textit{complex} of $I(G)$, denoted by $\Delta_{G}$, is the simplicial complex whose faces are the stable sets of $G$. Recall that a simplicial complex $\Delta$ is called \textit{pure} if every facet has the same number of elements. Thus, $\Delta_{G}$ is pure if and only if $G$ is well-covered. 

\vspace{0.2cm}

Some properties of $G$, $\Delta_{G}$ and $I(G)$ allow an interac\-tion between Commutative Algebra and Combinatorial Theory. Examples of these properties are: Cohen-Macaulayness, shellability, vertex decomposability and well-coveredness. These properties have been studied in (\cite{BH}, \cite{CC}, \cite{Doch}, \cite{Villa5}, \cite{HH}, \cite{ON}, \cite{MM}, \cite{Stanley}, \cite{V}, \cite{VT}, \cite{Villa}, \cite{RW}). In general, we have the following implications (see \cite{BH}, \cite{Stanley}, \cite{Villa}, \cite{RW})

\vspace{0.2cm}

$ \begin{array}{ccccccc}
\begin{array}{c}{\rm Unmixed}\\ {\rm vertex\, decomposable}\end{array} & \hspace{-0.2cm}\Rightarrow\hspace{-0.2cm} & \begin{array}{c}{\rm Pure}\\{\rm shellable} \end{array} & \hspace{-0.2cm}\Rightarrow\hspace{-0.2cm} & \textrm{Cohen\,-\,Macaulay} & \hspace{-0.2cm}\Rightarrow\hspace{-0.2cm} & \textrm{ Well\,-\,covered} \\
\end{array}$ 

\vspace{0.2cm}

The equivalence between the Cohen-Macaulay property and the unmixed vertex decomposable pro\-per\-ty has been studied for some families of graphs: bipartite graphs (in \cite{Villa5} and \cite{HH}); very well-covered graphs (in \cite{half} and \cite{MM}); graphs with girth at least $5$, block-cactus (in \cite{ON}); and graphs without 4-cycles and 5-cycles (in \cite{BC}). For this paper, a cycle $C=(z_{1},z_{2},...,z_{n})$ can have chords (edges between non-consecutive vertices in $C$) in $G$. A cycle without chords is called an \textit{induced cycle}.

\vspace{0.2cm}

If a bipartite graph is well-covered, pure shellable or Cohen-Macaulay, then it is K$\ddot{{\rm o}}$nig and has a perfect matching. The perfect matching is important because it allowed Hibi and Herzog to characterize Cohen-Macaulay bipartite graph (see \cite{HH}). Similarly, the existence of a perfect matching allows one to find a classification of well-covered bipartite graphs (see \cite{Ra} and \cite{Villa3}). However, a 3-cycle and a 5-cycle are Cohen-Macaulay graphs, but they does not have a perfect matching. This is the motivation for the study of Cohen-Macaulay graphs without 3-cycles and 5-cycles. In particular, we are interested in knowing if these graphs have a perfect matching. In this paper we prove that it is affirmative. 

\vspace{0.2cm}

The paper is organized as follow: in section 2 we give some properties and relations between critical, shedding and extendable vertices that we will use in the following sections. In section 3 we prove some results about well-covered graphs. In section 4 we prove the equivalences of unmixed vertex decomposable and Cohen-Macaulay properties for K$\ddot{{\rm o}}$nig graphs and graphs without 3-cycles and 5-cycles. We prove that theses properties are equivalent to the following condition: $G$ is an unmixed K$\ddot{{\rm o}}$nig graph with a perfect matching $e_{1},...,e_{g}$ without 4-cycles with two $e_{i}$'s. This result extends the criterion of Herzog-Hibi for Cohen-Macaulay bipartite graphs, given in \cite{HH}. In \cite{V} Van Tuyl proved that the vertex decomposable property, the shellable (non-pure) property and the sequentially Cohen-Macaulay property are equivalent in bipartite graphs. Fur\-ther\-more, in \cite{VT} Van Tuyl and Villarreal give a criterion that characterize shellable bipartite graphs. These results and results obtained in section 4, motive us to study the vertex decomposable property and the shellable (non-pure) property for graphs without 3-cycles and 5-cycles. In section 5, we prove that the neighborhood of a 2-connected block of $G$ has a free vertex, if $G$ is a bipartite shellable graph or if $G$ is a vertex decomposable graph without 3-cycles and 5-cycles. Also, we prove that the criterion of Van Tuyl-Villarreal can be extended to vertex decomposable graphs without 3-cycles and 5-cycles and shellable graphs with girth at least 11. The equivalence between the shellable pro\-perty and the vertex decomposable property for graphs without 3-cycles and 5-cycles is an open problem.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Critical, extendable and shedding vertices.}

Let $X$ be a subset of $V(G)$. The \textit{subgraph induced} by $X$ in $G$, denoted by $G[X]$ is the graph  with vertex set $X$ and whose edge set is $\{\{x,y\}\in E(G)\ |\ x,y\in X\}$. Furthermore, let $G\setminus X$ denote the induced subgraph $G[V(G)\setminus X]$. Now, if $v\in V(G)$, then the set of \textit{neighbors} of $v$ (in $G$) is denoted by $N_{G}(v)$ and its closed neighborhood is $N_{G}[v]=N_{G}(v) \cup \{v\}$. The \textit{degree} of $v$ in $G$ is deg$_{G}(v)=\vert N_{G}(v)\vert$. 

\begin{definition}  $G$ is vertex decomposable if $G$ is a  totally disconnected graph or there is a vertex $v$ such that 
\begin{description}
 \item{\rm (a)} $G\setminus v$ and $G\setminus N_{G}[v]$ are both vertex decomposable, and
 \item{\rm (b)} each stable set in $G\setminus N_{G}[v]$ is not a maximal stable set in $G\setminus v$.
\end{description}
\end{definition}

A \textit{shedding vertex} of $G$ is any vertex which satisfies the condition (b). Equivalently, $v$ is a shedding vertex if for every stable set $S$ contained in $G\setminus N_{G}[v]$, there is some $x\in N_{G}(v)$ such that $S\cup \{x\}$ is stable.


\begin{lemma} \label{4} If $x$ is a vertex of $G$, then $x$ is a shedding vertex if and only if $|N_{G}(x)\setminus N_{G}(S)|\geq 1$ for every stable set $S$ of $G\setminus N_{G}[x]$.
\end{lemma}

\begin{proof}
$\Rightarrow$) We take a stable set $S$ of $G\setminus N_{G}[x]$. Since $x$ is a shedding vertex, then there is a vertex $z\in N_{G}(x)$ such that $S\cup \{z\}$ is a stable set of $G\setminus x$. Thus, $z\notin N_{G}[S]$. Therefore, $|N_{G}(x)\setminus N_{G}(S)|\geq 1$. 

\vspace{0.2cm}

$\Leftarrow$) We take a stable set $S$ of $G\setminus N_{G}[x]$. Thus, there exists a vertex $z\in N_{G}(x)\setminus N_{G}(S)$. Since $z\in N_{G}(x)$, we have that $z\notin S$. Furthermore, $z\notin N_{G}(S)$, then $S\cup \{z\}$ is a stable set of $G\setminus x$. Consequently, $S$ is not a maximal stable set of $G\setminus x$. Therefore, $x$ is a shedding vertex.  
\end{proof}


\begin{definition} Let $S$ be a stable set of $G$. If $x$ is of degree zero in $G\setminus N_{G}[S]$, then $x$ is called \textit{isolated vertex} in $G\setminus N_{G}[S]$, or we say that $S$ \textit{isolates} to $x$. \end{definition}

By Lemma \ref{4}, we have that $x$ is not a shedding vertex if and only if there exists a stable set $S$ of $G\setminus N_{G}[x]$ such that $N_{G}(x)\subseteq N_{G}(S)$, i.e. $x$ is an isolated vertex in $G\setminus N_{G}[S]$.


\begin{corollary} Let $S$ be a stable set of $G$. If $S$ isolates $x$ in $G$, then $x$ is not a shedding vertex in $G\setminus N_{G}[y]$ for all $y\in S$.
\end{corollary}

\begin{proof}
Since $S$ isolates $x$, then deg$_{G\setminus N_{G}[S]}(x)=0$ and in particular $x\in V(G\setminus N_{G}[S])$. Thus, $N_{G}(x)\subseteq N_{G}[S]\setminus S$. Hence, if $y\in S$ and $G'=G\setminus N_{G}[y]$, then $x\in V(G')$. Furthermore, since $S\cap N_{G}[x]=\emptyset$, then $S'=S\setminus y$ is a stable set in $G'\setminus N_{G'}[x]$. Now, since $S$ isolates $x$, if $a\in N_{G'}(x)$, then there exists $s\in S$ such that $\{a,s\}\in E(G)$. But $a\in N_{G'}(x)$, then $a\notin N_{G}[y]$, consequently $s\in S'$ and $\{a,s\}\in E(G')$. This implies $\vert N_{G'}(x)\setminus N_{G'}(S') \vert =0$. Therefore, by Lemma \ref{4}, $x$ is not a shedding vertex in $G'$. \end{proof} 


\begin{theorem} \label{ext} If $x$ is a shedding vertex of $G$, then one of the following conditions hold: 
\begin{description}
 \item{\rm (a)} There is $y\in N_{G}(x)$ such that $N_{G}[y]\subseteq N_{G}[x]$.
 \item{\rm (b)} $x$ is in a 5-cycle with at most one chord.
\end{description}
\end{theorem}

\begin{proof} We take $N_{G}(x)=\{y_{1},y_{2},...,y_{k}\}$. If $G$ does not satisfy (a), then there is $\{z_{1},...,z_{k}\}$ $\subseteq V(G)\setminus N_{G}[x]$ such that $\{y_{i},z_{i}\}\in E(G)$ for $i\in\{1,...,k\}$. We denote by $L=\{z_{1},...,z_{q}\}=\{z_{1},...,z_{k}\}$ and suppose that $z_{i}\neq z_{j}$ for $1\leq i < j \leq q$. By Lemma \ref{4}, if $L$ is a stable set of $G$, then $\vert N_{G}(x)\setminus N_{G}(L)\vert \geq 1$. But $N_{G}(x)=\{y_{1},...,y_{k}\}\subseteq N_{G}(L)$, then $L$ is not a stable set. Hence, $q\geq 2$ and there exist $z_{i_1},z_{i_2}\in L$ such that $\{z_{i_1},z_{i_2}\}\in E(G)$. Thus, there exist $y_{j_1}$ and $y_{j_2}$ such that $y_{j_1}\neq y_{j_2}$ and $\{y_{j_1},z_{i_1}\}, \{y_{j_2},z_{i_2}\}\in E(G)$. Furthermore, $\{z_{i},y_{j_2}\},\{z_{i_2},y_{j_1}\},\{z_{i_1},x\},\{z_{i_2},x\}\notin E(G)$. Therefore, $(x,y_{j_1},z_{i_1},z_{i_2},y_{j_2})$ is a 5-cycle of $G$ with at most one chord. \end{proof}


\begin{definition}  A vertex $v$ is called simplicial if the induced subgraph $G[N_{G}(v)]$ is a complete graph (or clique). Equivalently, a simplicial vertex is a vertex that appears in exactly one clique.  \end{definition}


\begin{remark}\label{25} If $v,w \in V(G)$ such that $N_{G}[v]\subseteq N_{G}[w]$, then $w$ is a shedding vertex of G {\rm(see Lemma 6 in \cite{RW})}. In particular, if $v$ is a simplicial vertex, then any $w\in N_{G}(v)$ is a shedding vertex {\rm(see Corollary 7 in \cite{RW})}. \end{remark}


\begin{corollary} Let $G$ be graph without 4-cycles. If $x$ is a shedding vertex of $G$, then $x$ is in a 5-cycle or there exists a simplicial vertex $z$ such that $\{x,z\}\in E(G)$ with $|N_{G}[z]|\leq 3$. 
\end{corollary}

\begin{proof}
By Theorem \ref{ext}, if $x$ is not in a 5-cycle, then there is $z\in N_{G}(x)$ such that $N_{G}[z]\subseteq N_{G}[x]$. If deg$_{G}(z)=1$, then $z$ is a simplicial vertex. If deg$_{G}(z)=2$, then $N_{G}(z)=\{x,w\}$. Consequently, $(z,x,w)$ is a 3-cycle since $N_{G}[z]\subseteq N_{G}[x]$. Thus, $z$ is a simplicial vertex. Now, if deg$_{G}(z)\geq 3$, then there are $w_{1},w_{2}\in N_{G}(z)\setminus x$. Since $N_{G}[z]\subseteq N_{G}[x]$, we have that $(w_{1},z,w_{2},x)$ is a 4-cycle of $G$. This is a contradiction. Therefore, $\vert N_{G}[z]\vert \leq 3$ and $z$ is a simplicial vertex. \end{proof}


\begin{remark} \label{11} If $G$ is a 5-cycle with $V(G)=\{x_{1},x_{2},x_{3},x_{4},x_{5}\}$, then each $x_{i}$ is a shedding vertex. \end{remark}

\begin{proof}
We can assume that $i=1$, then $\{x_{3}\}$ and $\{x_{4}\}$ are the stable sets in $G\setminus N_{G}[x_{1}]$. Furthermore, $\{x_{3},x_{5}\}$ and $\{x_{2},x_{4}\}$ are stable sets in $G\setminus x_{1}$. Hence, each stable set of $G\setminus N_{G}[x_1]$ is not a maximal stable set in $G\setminus x_1$. Therefore, $x_{1}$ is a shedding vertex. \end{proof}


\begin{definition} A vertex $v$ of $G$ is critical if $\tau (G\setminus v)< \tau (G)$. Furthermore, $G$ is called a $vertex$ $critical$ graph if each vertex of $G$ is critical. 
\end{definition}


\begin{lemma} \label{10} If $\tau(G\setminus v)< \tau(G)$, then $\tau(G)=\tau (G\setminus v)+1$. Moreover, $v$ is a critical vertex if and only if $\beta(G)=\beta(G\setminus v)$. \end{lemma}

\begin{proof}
If $t$ is a minimal vertex cover such that $\vert t\vert=\tau(G\setminus v)$, then $t\cup \{v\}$ is a vertex cover of $G$. Thus, $\tau(G)\leq \vert t\cup \{v\}\vert =\tau(G\setminus v)+1$. Consequently, if $\tau(G)> \tau(G\setminus v)$, then $\tau(G)=\tau(G\setminus v)+1$.

\vspace{0.2cm}

Now, we have that $\tau (G)+\beta(G)=\vert V(G)\vert =\vert V(G\setminus v)\vert +1=\tau (G\setminus v)+\beta(G\setminus v)+1$. Hence, $\beta(G)=\beta(G\setminus v)$ if and only if $\tau (G) = \tau (G\setminus v)+1$. Therefore, $v$ is a critical vertex if and only if $\beta(G)=\beta(G\setminus v)$. \end{proof} 


\begin{definition} A vertex $v$ of $G$ is called an $extendable$ vertex if $G$ and $G\setminus v$ are well-covered graphs with $\beta (G)=\beta (G\setminus v)$. 
\end{definition}

Note that if $v$ is an extendable vertex, then every maximal stable set $S$ of $G\setminus v$ contains a vertex of $N_{G}(v)$.


\begin{corollary} \label{18} Let $G$ be an unmixed graph and $x\in V(G)$. The following conditions are equi\-va\-lent: 
\begin{description}
 \item{\rm (a)} $x$ is an extendable vertex.
 \item{\rm (b)} $|N_{G}(x)\setminus N_{G}(S)|\geq 1$ for every stable set $S$ of $G\setminus N_{G}[x]$.
 \item{\rm (c)} $x$ is a shedding vertex.
 \item{\rm (d)} $x$ is a critical vertex and $G\setminus x$ is unmixed.
\end{description}
\end{corollary}

\begin{proof}
$(a)\Leftrightarrow (b)$ (\rm \cite{Finbow}, Lemma 2). 

\vspace{0.2cm}

$(b)\Leftrightarrow (c)$ By Lemma \ref{4}. 

\vspace{0.2cm}

$(a)\Leftrightarrow (d)$  Since $G$ is unmixed, then by Lemma \ref{10}, $x$ is extendable if and only if $x$ is a critical vertex and $G\setminus x$ is unmixed. \end{proof}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\section{K\"onig and well-covered graphs}

In this paper we denoted by $Z_{G}$ the set of the isolated vertices of $G$, that is, $$Z_{G}=\{x\in V(G)\ \vert \ \deg_{G}(x)=0\}.$$


\begin{definition} $G$ is a \textit{K$\ddot{o}$nig} graph if $\tau(G)=\nu(G)$ where $\nu(G)$ is the maximum number of pairwise disjoint edges. A \textit{perfect matching of K$\ddot{o}$nig type} of $G$ is a collection $e_{1},...,e_{g}$ of pairwise disjoint edges whose union is $V(G)$ and $g=\tau(G)$. \end{definition}


\begin{proposition} \label{22} Let $G$ be a K$\ddot{o}$nig graph and $G'=G\setminus Z_{G}$. Then the following are equivalent:
\begin{description}
 \item{\rm (a)} $G$ is unmixed.
 \item{\rm (b)} $G'$ is unmixed.
 \item{\rm (c)} If $V(G')\neq \emptyset$, then $G'$ has a perfect matching $e_{1},...,e_{g}$ of K$\ddot{o}$nig type such that for any two edges $f_{1}\neq f_{2}$ and for two distinct vertices $x\in f_{1}$, $y\in f_{2}$ contained in some $e_{i}$, one has that $(f_{1}\setminus x)\cup (f_{2}\setminus y)$ is an edge.
\end{description}
\end{proposition}

\begin{proof}
(a)$\Leftrightarrow$(b) Since $V(G)\setminus V(G')=Z_{G}$, then $C$ is a vertex cover of $G$ if and only if $C$ is a vertex cover of $G'$. Therefore, $G$ is unmixed if and only if $G'$ is unmixed. 

\vspace{0.2cm}

(b)$\Leftrightarrow$(c) By (\cite{MR}, Lemma 2.3 and Proposition 2.9). 
\end{proof} 


\begin{definition} A graph $G$ is called \textit{very well-covered} if it is well-covered without isolated vertices and $|V(G)|= 2{\rm ht}(I(G))$. \end{definition}


\begin{lemma} \label{12} $G$ is an unmixed K$\ddot{o}$nig graph if and only if $G$ is totally disconnected or $G'=G\setminus Z_{G}$ is very well-covered.
\end{lemma}

\begin{proof}
$\Rightarrow$) If $G$ is not totally disconnected, then from Proposition \ref{22}, $G'$ has a perfect matching $e_{1},...,e_{g}$ of K$\ddot{{\rm o}}$nig type. Hence, $|V(G')|=2g=2\tau(G')=2{\rm ht}(I(G'))$. Furthermore, $G'$ is unmixed, therefore $G'$ is very well-covered. 

\vspace{0.2cm}

$\Leftarrow$) If $G$ is totally disconnected, then $\nu(G)=0$ and $\tau(G)=0$. Hence, $G$ is an unmixed K$\ddot{{\rm o}}$nig graph. Now, if $G$ is not totally disconnected, then $G'$ is very well-covered. Consequently, by (\cite{GV}, Corollary 3.7) $G'$ has a perfect matching. Thus, $\nu (G')= \vert V(G')\vert /2={\rm ht} (G')=\tau(G')$. Hence, $G'$ is K$\ddot{{\rm o}}$nig. Furthermore, $\nu(G)=\nu(G')$ and $\tau(G)=\tau(G')$, then $G$ is K$\ddot{{\rm o}}$nig. Finally, since $G'$ is unmixed, by Proposition \ref{22}, $G$ is also unmixed. \end{proof} 


\begin{definition} A subgraph $H$ of $G$ is called a c-minor (of $G$) if there exists a stable set $S$ of $G$, such that $H=G\setminus N_{G}[S]$.
\end{definition}


\begin{remark}\label{19} Each connected component of a graph $G$ is a c-minor of $G$. \end{remark}


\begin{remark} \label{27} The unmixed property is closed under c-minors. That is, each c-minor of $G$ has the same property {\rm (see \cite{Villa})}.
\end{remark} 


\begin{definition} A vertex of degree one is called \textit{leaf} or \textit{free vertex}. Furthermore, an edge which is incident with a leaf is called \textit{pendant}. 
\end{definition}


\begin{lemma} \label{21} If $G$ is an unmixed graph and $x\in V(G)$, then $N_{G}(x)$ does not contain two free vertices.
\end{lemma}

\begin{proof}
We suppose that there exists $x\in V(G)$ such that $y_{1},...,y_{s}$ are free vertices in $N_{G}(x)$. Hence, $G_{1}=G\setminus N_{G}[y_{1},...,y_{s}]=G\setminus \{x,y_{1},...,y_{s}\}$ is unmixed. Now, we take a maximal stable set $S$ of $G_1$. Thus, $\vert S\vert=\beta(G_1)$ since $G_1$ is unmixed. Consequently, $S_{1}=S\cup \{y_{1},...,y_{s}\}$ is a stable set in $G$. We take $S_{2}$ a maximal stable in $G$ such that $x\in S_{2}$. Since $G$ is unmixed, we have that $\vert S_{2}\vert\geq \vert S_{1} \vert=\vert S \vert+s$. Furthermore, $S_{2}\setminus x$ is a stable set in $G_1$, then $|S_{2}|\leq \beta(G_{1})+1$. This implies  $\beta(G_{1})+1 \geq \vert S\vert +s$. But, $\vert S \vert=\beta(G_{1})$, therefore, $s\leq 1$. \end{proof} 


\begin{definition} If $v,w\in V(G)$, then the distance d$(u,v)$ between $u$ and $v$ in $G$ is the length of the shortest path joining them, otherwise $d(u,v)=\infty$. Now, if $H\subseteq G$, then the distance from a vertex $v$ to $H$ is $d(v,H)=min\{d(v,u)\ \vert \ u\in V(H)\}$. Furthermore, if $W\subseteq V(G)$, then we define $d(v,W)=d(v,G[W])$ and $D_{i}(W)=\{v\in V(G)\ \vert \ d(v,W)=i\}$. \end{definition}


\begin{proposition} \label{7} Let $G$ be an unmixed connected graph without 3-cycles and 5-cycles. If $C$ is a 7-cycle and $H$ is a c-minor of $G$ with $C\subseteq H$ such that $C$ has three non-adjacent  vertices of degree 2 in $H$, then $C$ is a c-minor of $G$.
\end{proposition}

\begin{proof}
We take a minimal c-minor $H$ of $G$ such that $C\subseteq H$ and $C$ has three non-adjacent vertices of degree 2 in $H$. We can suppose that $C=(x,z_{1},w_{1},a,b,w_{2},z_{2})$ with deg$_{H}(x)=$ deg$_{H}(w_{1})$ $=$ deg$_{H}(w_{2})$ $=2$. If $\{z_{1},b\}\in E(H)$, then $(z_{1},b,w_{2},z_{2},x)$ is a 5-cycle of $G$. Thus, $\{z_{1},b\}\notin E(H)$, si\-mi\-larly $\{z_{2},a\}\notin E(H)$. Furthermore, since $G$ does not have 3-cycles, then $\{z_{1},z_{2}\},\{z_{1},a\}$, $\{z_{2},b\}\notin E(H)$. Hence, $C$ is an induced cycle in $H$. On the other hand, if there exists $v\in V(H)$ such that $d(v,C)\geq 2$, then $H'=H\setminus N_{G}[v]$ is a c-minor of $G$ and $C\subseteq H'\subset H$. This is a contradiction by the minimality of $H$. Therefore, $d(v,C)\leq 1$ for each $v\in V(H)$. 

\vspace{0.2cm}
 
Now, if deg$_{H}(b)\geq 3$, then there exists $c\in V(H)\setminus V(C)$ such that $\{b,c\}\in E(H)$. If $\{c,z_{2}\}\notin E(G)$ implies that $N_{H_{1}}(z_{2})$ has two free vertices, $w_{2}$ and $x$, in $H_{1}=H\setminus N_{H}[w_{1},c]$, this is a contradiction by Lemma \ref{21}. Thus $\{c,z_{2}\}\in E(H)$. Furthermore, $\{a,c\}$, $\{z_{1},c\}\notin E(H)$ since $(a,b,c)$ and $(z_{1},w_{1},a,b,c)$ are not cycles in $G$. Hence, if deg$_{H}(c)\geq 3$, then there exists $d \in V(H)\setminus V(C)$ such that $\{c,d\}\in E(H)$. Also, $\{d,b\},\{d,z_{2}\},\{d,z_{1}\} \notin E(H)$ since $(c,b,d)$, $(z_{2},d,c)$ and $(z_{1},x,z_{2},c,d)$ are not cycles of $G$. But $d(d,C)\leq 1$, so $\{a,d\}\in E(H)$. Consequently, $N_{H_{2}}(z_{1})$ has two free vertices, $w_{1}$ and $x$, in $H_{2}=H\setminus N_{H}[d,w_{2}]$, a contradiction by Lemma \ref{21}, then deg$_{H}(c)=2$. This implies, $N_{H_{3}}(z_{2})$ has two free vertices, $w_{2}$ and $c$, in $H_{3}=H\setminus N_{H}[a]$. This is not possible, therefore deg$_{H}(b)=2$. Similarly, deg$_{H}(a)=2$. 

\vspace{0.2cm}

Now, if deg$_{H}(z_{2})\geq 3$ we have that there exists $c'\in V(H)\setminus V(C)$ such that $\{c',z_{2}\}\in E(H)$. If there exists $d'\in V(H)\setminus V(C)$ such that $\{c',d'\}\in E(H)$, then $\{d',z_{1}\}$ or $\{d',z_{2}\}\in E(G)$, since $d(d',C)\leq 1$. But $(c',d',z_{2})$ and $(x,z_{2},c',d',z_{1})$ are not cycles of $H$, thus, $N_{H}(c')\subseteq \{z_{1},z_{2}\}$. Consequently, $N_{H_{4}}(z_{2})$ has two free vertices, $x$ and $c'$, in $H_{4}=H\setminus N_{H}[w_{1}]$, a contradiction. Hence deg$_{H}(z_{2})=2$. Similarly, deg$_{H}(z_{1})=2$. Furthermore, since $H$ is minimal, then it is connected. Therefore, $H=C$ and $C$ is a c-minor of $G$. \end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{K\"onig and Cohen-Macaulay graphs without 3-cycles and 5-cycles}


\begin{definition} A simplicial complex $\Delta$ is shellable if the facets (maximal faces) of $\Delta$ can be ordered $F_{1},...,F_{s}$ such that for all $1\leq i<j\leq s$, there exists some $v\in F_{j}\setminus F_{i}$ and some $l\in \{1,...,j-1\}$ with $F_{j}\setminus F_{l}=\{v\}$. In this case, $F_{1},...,F_{s}$ is called  a shelling of $\Delta$.  A graph $G$ is called shellable if $\Delta_{G}$ is shellable. Furthermore, the facet set of $\Delta$ is denoted by $\mathcal{F}(\Delta)$. \end{definition}


\begin{remark} \label{27-1} The following properties: shellable, Cohen-Macaulay, sequentially Cohen-Macaulay and vertex decomposable are closed under c-minors \rm (see \cite{Biermann}, \cite{Villa}).
\end{remark} 


\begin{remark} \label{half} If $G$ is very well-covered with a perfect matching $e_{1},...,e_{g}$, then the following conditions are equivalent: 
\begin{description}
 \item{\rm (1)} $G$ is Cohen-Macaulay.
 \item{\rm (2)} There are no 4-cycles with two $e_{i}$'s. 
\end{description}
\end{remark}

\begin{proof}
By (\cite{half}, Theorem 3.4). \end{proof} 


\begin{proposition} \label{2} Let $G$ be a K$\ddot{o}$nig graph where $G'=G\setminus Z_{G}$. Then the following properties are equi\-valent:
\begin{description}
 \item{\rm (i)} $G$ is unmixed vertex decomposable.
 \item{\rm (ii)} $\Delta_G$ is pure shellable.
 \item{\rm (iii)} $R/I(G)$ is Cohen-Macaulay.
 \item{\rm (iv)} $V(G')=\emptyset$ or $G'$ is an unmixed graph with a perfect matching $e_{1},...,e_{g}$ of K$\ddot{o}$nig type without 4-cycles with two $e_{i}$'s.
 \item{\rm (v)} $V(G')=\emptyset$ or there exists a relabelling of the vertices $V(G')=\{x_{1},...,x_{h},y_{1},...,y_{h}\}$ such that $\{x_{1},y_{1}\},...,\{x_{h},y_{h}\}$ is a perfect matching, $X=\{x_{1},...,x_{h}\}$ is a minimal vertex cover of $G'$ and the following conditions holds:
\begin{description}
 \item{\rm (a)} If $a_{i}\in \{x_{i},y_{i}\}$ and $\{a_{i},x_{j}\}, \{y_{j},x_{k}\}\in E(G')$, then $\{a_{i},x_{k}\}\in E(G')$ for $i\neq j$ and $j\neq k$;
 \item{\rm (b)} If $\{x_{i},y_{j}\}\in E(G')$, then $i\leq j$.
\end{description} 
\end{description}
\end{proposition}

\begin{proof}
(i)$\Leftrightarrow$(ii)$\Leftrightarrow$(iii) In each case $G$ is unmixed and K$\ddot{{\rm o}}$nig. Hence, by Lemma \ref{12}, $G$ is totally disconnected or $G'$ is very well-covered. If $G$ is totally disconnected, then we obtain the equivalences. Now, if $G'$ is very well-covered, then by (\cite{MM}, Theorem 1.1) we obtain the equivalences. 

\vspace{0.2cm}

(iv)$\Rightarrow$(iii) We can assume that $V(G')\neq \emptyset$. Thus, by Lemma \ref{12}, $G'$ is very well-covered. Hence, by Remark \ref{half} $G'$ is Cohen-Macaulay. Therefore, $G$ is Cohen-Macaulay. 

\vspace{0.2cm}

(iii)$\Rightarrow$ (v) Since $R/I(G)$ is Cohen-Macaulay, then $G$ is unmixed. Consequently, by Lemma \ref{12}, we can assume that $G'$ is very well-covered. Hence, by (\cite{MM}, Lemma 3.1), $G'$ satisfies (v). 

\vspace{0.2cm}

(v)$\Rightarrow$(iv) We can assume that $V(G')\neq \emptyset$. Since,  $e_{1}=\{x_{1},y_{1}\},...,e_{h}=\{x_{h},y_{h}\}$ is a perfect matching, then $\nu(G')=h$. Furthermore, $X$ is a minimal vertex cover, so $\tau(G')=h$. Hence, $e_{1},...,e_{h}$ is a perfect matching of K$\ddot{{\rm o}}$nig type. Thus, from (a) and Proposition \ref{22}, $G'$ is unmixed. On the other hand $\{y_{1},...,y_{h}\}$ is a stable set. Therefore, from (b), there are no 4-cycles with two $e_{i}$'s. 
\end{proof}


\begin{corollary} \label{cuadrado} Let $G$ be a connected K$\ddot{o}$nig graph. If $G$ is Cohen-Macaulay, then $G$ is an isolated vertex or $G$ has at least one free vertex. \end{corollary}

\begin{proof}
By Proposition \ref{2}, if $G$ is not an isolated vertex, then $G$ has a perfect mat\-ching $e_{1}=\{x_{1},y_{1}\},...,e_{h}=\{x_{h},y_{h}\}$ where $\{x_{1},...,x_{h}\}$ is a minimal vertex cover. Thus, $\{y_{1},...,y_{h}\}$ is a maximal stable set. Furthermore, if $\{x_{i},y_{j}\}$, then $i\leq j$. Hence, $N_{G}(y_{1})=\{x_{1}\}$. Therefore, $y_{1}$ is a free vertex. \end{proof}


\begin{lemma} \label{6} Let $G$ be an unmixed connected graph with a perfect mat\-ching $e_{1}$, ..., $e_{g}$ of K$\ddot{o}$nig type without 4-cycles with two $e_{i}$'s and $g\geq 2$. For each $z\in V(G)$ we have that: 
\begin{description}
 \item{\rm (a)} If $\deg_{G}(z)\geq 2$, then there exist $\{z,w_{1}\},\{w_{1},w_{2}\}\in E(G)$ such that $\deg_{G}(w_{2})$ $=1$. Furthermore, $e_{i}=\{w_{1},w_{2}\}$ for some $i\in \{1,...,g\}$.
 \item{\rm (b)} If $\deg_{G}(z)=1$, then there exist $\{z,w_{1}\}$,$\{w_{1},w_{2}\}$,$\{w_{2},w_{3}\}\in E(G)$ such that $\deg_{G}(w_{3})$ $=1$. Moreover, $e_{i}=\{z,w_{1}\}$ and $e_{j}=\{w_{2},w_{3}\}$ for some $i,j\in \{1,...,g\}$.
\end{description}
\end{lemma}

\begin{proof}
Since $e_{1}=\{x_{1},y_{1}\},...,e_{g}=\{x_{g},y_{g}\}$ is a perfect matching of K$\ddot{{\rm o}}$nig type we can assume $D=\{x_{1},...,x_{g}\}$ is a minimal vertex cover. Thus, $F=\{y_{1},...,y_{g}\}$ is a maximal stable set. By Proposition \ref{2}, we can assume that if $\{x_{i},y_{j}\}\in E(G)$, then $i\leq j$. Now, we take a vertex $z\in V(G)$. 

\vspace{0.2cm}

(a) First, we suppose that $z=x_{k}$ and there is a vertex $x_{j}$ in $N_{G}(x_{k})$. If $y_{j}$ is a free vertex, then we take $w_{1}=x_{j}$ and $w_{2}=y_{j}$, and $e_{j}=\{w_{1},w_{2}\}$. Now, we can assume $N_{G}(y_{j})\setminus x_{j}=\{x_{p_1},...,x_{p_r}\}$ with $p_{1}<\cdots < p_{r}< j$. If $y_{p_1}$ is not a free vertex, then there is a vertex $x_{p}$ with $p<p_{1}$ such that $\{x_{p},y_{p_1}\}\in E(G)$. Since $G$ is unmixed, from Proposition \ref{22}, we obtain that $\{x_{p},y_{j}\}=(\{x_{p},y_{p_1}\}\setminus y_{p_1})\cup (\{y_{j},x_{p_1}\}\setminus x_{p_1})\in E(G)$. But $p<p_{1}$, a contradiction since $p_{1}$ is minimal. Consequently, deg$_{G}(y_{p_1})=1$. Also, from Proposition \ref{22}, we have that $\{x_{k},x_{p_1}\}=(\{x_{k},x_{j}\}\setminus x_{j})\cup (\{x_{p_1},y_{j}\}\setminus y_{j})\in E(G)$. Hence, we take $w_{1}=x_{p_1}$ and $w_{2}=y_{p_1}$, and we have that $e_{p_1}=\{w_{1},w_{2}\}$. Now, we assume that $z=x_{k}$ and $N_{G}(x_{k})\setminus y_{k}=\{y_{j_1},...,y_{j_t}\}$ with $k < j_{1}< \cdots < j_{t}$. We suppose that deg$_{G}(x_{j_t})\geq 2$. If there is a vertex $y_{r}$ such that $\{x_{j_t},y_{r}\}\in E(G)$, then $r>j_{t}$. Since $G$ is unmixed, $\{x_{k},y_{r}\}=(\{x_{k},y_{j_t}\}\setminus y_{j_t}) \cup (\{y_{r},x_{j_t}\}\setminus x_{j_t}) \in E(G)$, a contradiction since $j_{t}$ is maximal. Thus, there exists a vertex $x_{p}$ such that $\{x_{j_t},x_{p}\}\in E(G)$. But, since $G$ is unmixed, then $\{x_{k},x_{p}\}=(\{x_{k},y_{j_t}\}\setminus y_{j_t})\cup(\{x_{p},x_{j_t}\}\setminus x_{j_t})\in E(G)$. This is a contradiction since $N_{G}(x_{k})\setminus y_{k}=\{y_{j_1},...,y_{i_t}\}$. Consequently, deg$_{G}(x_{j_t})=1$. Therefore, we take $w_{1}=y_{j_t}$ and $w_{2}=x_{j_t}$, with $e_{j_t}=\{w_{1},w_{2}\}$. 

\vspace{0.2cm}

Finally, we assume that $z=y_{k}$, since $y_{k}$ is not a free vertex, then $N_{G}(y_{k})\setminus x_{k}=\{x_{j_1},...,x_{j_r}\}$ with $j_{1}< \cdots <j_{r}<k$. If $y_{j_1}$ is not a free vertex, then there is a vertex $x_{q}$ such that $\{x_{q},y_{j_1}\}\in E(G)$ with $q<j_{1}$. This implies $\{x_{q},y_{k}\}=(\{x_{q},y_{j_1}\}\setminus y_{j_1})\cup (\{x_{j_1},y_{k}\}\setminus x_{j_1})\in E(G)$. But $q<j_{1}$, a contradiction. Therefore, deg$_{G}(y_{j_1})=1$ and we take $w_{1}=x_{j_1}$ and $w_{2}=y_{j_1}$. Hence, $e_{j_1}=\{w_{1},w_{2}\}$. 

\vspace{0.2cm}

(b) Since $e_{1},...,e_{g}$ is a perfect matching, then there exists $i\in \{1,...,g\}$ such that $e_{i}=\{z,z'\}$. Since $G$ is connected, $z$ is a free vertex and $g\geq 2$, then $\deg_{G}(z')\geq 2$. Thus, by (a)  there exist $w_{1}',w_{2}'\in V(G)$ such that $\{z',w_{1}'\},\{w_{1}',w_{2}'\}\in E(G)$ where deg$_{G}(w_{2}')=1$ and $\{w_{1}',w_{2}'\}=e_{j}$ for some $j\in \{1,...,g\}$.  Therefore, we take $w_{1}=z'$, $w_{2}=w_{1}'$, $w_{3}=w_{2}'$. Consequently, $e_{i}=\{z,w_{1}\}$ and $e_{j}=\{w_{2},w_{3}\}$. \end{proof}


\begin{remark} \label{29} If $C_{n}$ is a n-cycle, then $C_{n}$ is vertex decomposable, shellable or sequentially Cohen-Macaulay if and only if $n=3$ or $5$ {\rm(see \cite{Chris} and \cite{RW})}. Furthermore, a chordal graph, which is a graph whose induced cycles are 3-cycles, is vertex decomposable {\rm(see Coro\-lla\-ry 7 in \cite{RW})}. In particular trees are vertex decomposable. \end{remark}


\begin{theorem} \label{P1} Let $G$ be a graph without 3-cycles and 5-cycles. If $G_{1},...,G_{k}$ are the connected components of $G$, then the following conditions are equi\-va\-lent:  
\begin{description}
 \item{\rm (a)} $G$ is unmixed vertex decomposable.
 \item{\rm (b)} $G$ is pure shellable.
 \item{\rm (c)} $G$ is Cohen-Macaulay
 \item{\rm (d)} $G$ is unmixed and if $G_{i}$ is not an isolated vertex, then $G_{i}$ has a perfect matching $e_{1},...,e_{g}$ of K$\ddot{o}$nig type without 4-cycles with two $e_{i}'s.$
\end{description}
\end{theorem}

\begin{proof}
(a) $\Rightarrow$ (b) $\Rightarrow$ (c) (see \cite{Stanley}, \cite{Villa}, \cite{RW}). 

\vspace{0.2cm}

(d) $\Rightarrow$ (a) Since each component $G_{i}$ is K$\ddot{{\rm o}}$nig, then $G$ is K$\ddot{{\rm o}}$nig. Therefore, from Proposition \ref{2}, $G$ is unmixed vertex decomposable. 

\vspace{0.2cm}

(c) $\Rightarrow$ (d) Since $G$ is Cohen-Macaulay, then $G$ is unmixed. We proceed by induction on $\vert V(G)\vert$. We take $x\in V(G)$ such that deg$_{G}(x)$ is minimal and we suppose that $N_{G}(x)=\{z_{1},...,z_{r}\}$. By Remark \ref{27-1}, $G'=G\setminus N_{G}[x]$ is a Cohen-Macaulay graph. We take $G_{1}',...,G_{s}'$, the connected components of $G'$. We can assume that $V(G_{i}')=\{y_{i}\}$ for $i\in \{1,...,s'\}$. Since deg$_{G}(x)$ is minimal, this implies $\{y_{i},z_{j}\}\in E(G)$ for all $i\in \{1,...,s'\}$ and $j\in \{1,...,r\}$. Since $G$ does not contain 3-cycles, we have that $N_{G}(x)$ is a stable set. If $s'=s$, then the only maximal stable sets of $G$ are $\{y_{1},...,y_{s'},x\}$ and $\{z_{1},...,z_{r}\}$. Thus, $G$ is a bipartite graph. So, $G$ is K$\ddot{{\rm o}}$nig. Hence, by Proposition \ref{2}, $G$ satisfies (d). Consequently, we can assume $s>s'$, implying that there is a component $G_{i}'$ with an edge $e=\{w,w'\}$. 

\vspace{0.2cm}

Now, we suppose that $r\geq 2$. Since deg$_{G}(x)$ is minimal there exist $a,b\in V(G)$ such that $\{a,w\},\{b,w'\}\in E(G)$. If $a=b$, then $(a,w,w')$ is a 3-cycle in $G$. Hence, $a\neq b$. If $a,b\in N_{G}(x)$, then $(x,a,w,w',b)$ is a 5-cycle in $G$. Thus, $|\{w,w',a,b\}\cap V(G_{i}')|\geq 3$. By induction hypothesis, $G'$ satisfies (d). So, $G_{i}'$ has a perfect matching and $\tau(G_{i}')\geq 2$. Furthermore, by Corollary \ref{cuadrado}, $G_{i}'$ has a free vertex $a'$. Then, by Lemma \ref{6} (b), there exist edges $\{a',w_{1}\},\{w_{1},w_{2}\},\{w_{2},b'\}\in E(G_{i}')$ such that deg$_{G_{i}'}(a')=$ deg$_{G_{i}'}(b')=1$. By the minimality of deg$_{G}(x)$ we have that $a'$ and $b'$ are adjacent with at least $r-1$ neighbor vertices of $x$. If $r\geq 3$, then there exists $z_{j}$ such that $z_{j}\in N_{G}(a')\cap N_{G}(b')$. This implies that $(a',w_{1},w_{2},b',z_{j})$ is a 5-cycle of $G$. But $G$ does not have 5-cycles, consequently, $r=2$. We can assume that $\{a',z_{1}\}, \{b',z_{2}\}\in E(G)$, implying $C=(x,z_{1},a',w_{1},w_{2},b',z_{2})$ is a 7-cycle with deg$_{G}(a')=$ deg$_{G}(b')=$ deg$_{G}(x)=2$. Hence, by Proposition \ref{7}, $C$ is a c-minor of $G$. Thus, by Remark \ref{27-1}, $C$ is Cohen-Macaulay. This is a contradiction by Remark \ref{29}. Therefore, deg$_{G}(x)=r\leq 1$. 

\vspace{0.2cm}

If $r=0$, then the result is clear. Now, if $r=1$ we can assume that $G_{1},...,G_{k}$ are the connected components of $G$ and $z_{1}\in V(G_{1})$. Consequently, the connected components of $G\setminus N_{G}[x]$ are $F_{1},...,F_{l},G_{2},...,G_{k}$ where $F_{1},...,F_{l}$ are the connected components of $G_{1}\setminus N_{G_1}[x]$. By induction hypothesis $G_{2},...,G_{k}$ satisfy (d). If $F_{j}=\{d_{j}\}$, then $N_{G}(z_{1})$ has two free vertices, $d_{j}$ and $x$, a contradiction by Lemma \ref{21}. Hence, $\vert V(F_{i})\vert \geq 2$ for $i\in \{1,...,l\}$. By induction hypothesis, we have that $F_{i}$ has a perfect matching $M_{i}=\{e_{1}^{i},...,e_{g_{i}}^{i}\}$ of K$\ddot{{\rm o}}$nig type. Thus, $\{e\}\cup (\bigcup_{i=1}^{l}M_{i})$ is a perfect matching of $G_{1}$, where $e=\{x,z_{1}\}$. Also, $\{z_{1}\}\cup (\bigcup_{i=1}^{l}X_{i})$ is a vertex cover of $G_{1}$, where $X_{i}$ is a minimal vertex cover of $F_{i}$. Consequently, $\nu(G_{1}) \geq 1+\sum_{i=1}^{l}\vert M_{i}\vert= 1+\sum_{i=1}^{l}g_{i}=1+\sum_{i=1}^{l}\vert X_{i}\vert\geq \tau(G_{1})$. This implies that $G_{1}$ is K$\ddot{{\rm o}}$nig. Furthermore, by Remark \ref{27-1}, we have that $G_{1}$ is Cohen-Macaulay. Therefore, by Proposition \ref{2}, $G_{1}$ satisfies (d).  \end{proof}


\begin{corollary} Let $G$ be a connected graph without 3-cycles and 5-cycles. If $G$ is Cohen-Macaulay, then $G$ has at least one extendable vertex $x$ adjacent to a free vertex.
\end{corollary}
 
\begin{proof}
From Theorem \ref{P1}, $G$ is K$\ddot{{\rm o}}$nig. Thus, by Corollary \ref{cuadrado} there exists a free vertex $x$. If $N_{G}(x)=\{y\}$, then by Remark \ref{25}, $y$ is a shedding vertex. Therefore, from Corollary \ref{18}, $y$ is an extendable vertex, since $G$ is unmixed. \end{proof} 


\begin{definition} $G$ is called \textit{whisker graph} if there exists an induced subgraph $H$ of $G$ such that $V(H)=\{x_{1},...,x_{s}\}$, $V(G)=V(H)\cup \{y_{1},...,y_{s}\}$ and $E(G)=E(H)\cup W(H)$ where $W(H)=\{\{x_{1},y_{1}\},...,\{x_{s},y_{s}\}\}$. The edges of $W(H)$ are called whiskers and they form a perfect matching. \end{definition}


\begin{definition} The $girth$ of $G$ is the length of the smallest cycle or infinite if $G$ is a forest. \end{definition}


\begin{corollary} Let $G$ be a connected graph of girth 6 or more. If $G$ is not an isolated vertex, then the following conditions are equivalent:
\begin{description}
 \item{\rm (i)} $G$ is unmixed vertex decomposable.
 \item{\rm (ii)} $\Delta_G$ is pure shellable.
 \item{\rm (iii)} $R/I(G)$ is Cohen-Macaulay.
 \item{\rm (iv)} $G$ is an unmixed K$\ddot{o}$nig graph.
 \item{\rm (v)}  $G$ is very well-covered.
 \item{\rm (vi)}  $G$ is unmixed with $G\neq C_{7}$.
 \item{\rm (vii)} $G$ is a whisker graph.
\end{description}
\end{corollary}

\begin{proof}
(i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) (see \cite{Stanley}, \cite{Villa}, \cite{RW}). (iii) $\Rightarrow$ (iv) $G$ is unmixed and from Theorem \ref{P1}, $G$ is K$\ddot{{\rm o}}$nig. (iv) $\Rightarrow$ (v) From Lemma \ref{12}. (v) $\Rightarrow$ (vi) It is clear, since $C_{7}$ is not very well-covered.

\vspace{0.2cm}

(vi) $\Rightarrow$ (vii) By (\cite{Finbow}, Corollary 5), the pendant edges $\{x_{1},y_{1}\},...,\{x_{g},y_{g}\}$ of $G$ form a perfect matching. Since $\{x_{i},y_{i}\}$ is a pendant edge, we can assume that $\deg_{G}(y_{i})=1$ for each $1\leq i \leq g$. We take $H=G[x_{1},...,x_{n}]$. Therefore, $G$ is a whisker graph with $W(H)=\{\{x_{1},y_{1}\},...,\{x_{g},y_{g}\}\}$. 

\vspace{0.2cm}

(vii) $\Rightarrow$ (i) By (\cite{Doch}, Theorem 4.4). \end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\section{Vertex decomposable and shellable properties in graphs without 3-cycles and 5-cycles}

\begin{definition} A 5-cycle $C$ of $G$ is called \textit{basic} if $C$ does not contain two adjacent vertices of degree three or more in $G$. 
\end{definition}


\begin{lemma} \label{17} If $G$ is a graph, then any vertex of degree at least 3 in a basic 5-cycle is a shedding vertex.
\end{lemma}

\begin{proof}
Let $C=(x_{1},x_{2},x_{3},x_{4},x_{5})$ be a basic 5-cycle. We suppose that deg$_{G}(x_{1})$ $\geq 3$, since $C$ is a basic 5-cycle, then $\deg_{G}(x_2)=\deg_{G}(x_5)=2$. Also, we can assume that $\deg_{G}(x_{3})=2$. We take a stable set $S$ of $G\setminus N_{G}[x_{1}]$. Since $\{x_{3},x_{4}\}\in E(G)$, then $\vert S\cap \{x_{3},x_{4}\}\vert \leq 1$. Hence, $x_{3}\notin S$ or $x_{4}\notin S$. Consequently, $S\cup \{x_{2}\}$ or $S\cup \{x_{5}\}$ is a stable set of $G\setminus x_{1}$. Therefore, $x_{1}$ is a shedding vertex. \end{proof} 


\begin{remark} \label{35} If $G$ has a shedding vertex $v$ where $G \setminus v$ and $G\setminus N_{G}[v]$ are shellable with shelling $F_{1},...,F_{k}$ and $G_{1},...,G_{q}$, respectively, then $G$ is shellable with shelling $F_{1},...,F_{k},G_{1}\cup\{v\},...,G_{q}\cup\{v\}$ {\rm(see Lemma 6 in \cite{wachs})}. \end{remark}


\begin{theorem} \label{8} Let $G$ be a connected graph with a basic 5-cycle $C$. $G$ is a shellable graph if and only if there is a shedding vertex $x\in V(C)$ such that $G\setminus x$ and $G\setminus N_{G}[x]$ are shellable graphs.
\end{theorem}
 
\begin{proof}
$\Rightarrow$) We can suppose that $C=(x_{1},x_{2},x_{3},x_{4},x_{5})$. If $G=C$, then $G$ is shellable. By Remark \ref{11}, each vertex is a shedding vertex. Furthermore, $G\setminus x_{1}$ is a path with shelling $\{x_{2},x_{4}\}, \{x_{2},x_{5}\}, \{x_{3},x_{5}\}$ and $G\setminus N_{G}[x_{1}]$ is an edge. Therefore, $G\setminus x_{1}$ and $G\setminus N_{G}[x_{1}]$ are shellable graphs. Now, we suppose $G\neq C$. We can assume that deg$_{G}(x_{1})\geq 3$. Since $C$ is a basic 5-cycle, then deg$_{G}(x_{2})=$ deg$_{G}(x_{5})=2$. Also, we can suppose deg$_{G}(x_{3})=2$ and deg$_{G}(x_{4})\geq 2$. By Lemma \ref{17}, $x_{1}$ is a shedding vertex. Furthermore by Remark \ref{27-1}, we have that $G\setminus N_{G}[x_{1}]$ is a shellable graph. Now, we will prove that $G_{1}=G\setminus x_{1}$ is shellable. Since $G$ is shellable and since shellability is closed under c-minors, then $G_{2}=G\setminus N_{G}[x_{2}]$ is shellable. We assume that $F_{1},...,F_{r}$ is a shelling of $\Delta_{G_{2}}$. Also, $G_{3}=G\setminus N_{G}[x_{3},x_{5}]$ is shellable. We suppose that $H_{1}, H_{2},...,H_{k}$ is shelling of $\Delta_{G_{3}}$. We take $F\in \mathcal{F}(\Delta_{G_1})$. If $x_{2}\in F$, then $F\setminus x_{2}\in \mathcal{F}(\Delta_{G_{2}})$ and there exists $F_{i}$ such that $F=F_{i}\cup \{x_{2}\}$. If $x_{2}\notin F$, then $x_{3}\in F$ and $x_{4}\notin F$. Thus, $x_{5}\in F$. Hence, $F\setminus \{x_{3},x_{5}\}\in \mathcal{F}(\Delta_{G_{3}})$, then there exists $H_{j}$ such that $F=H_{j}\cup \{x_{3},x_{5}\}$. This implies, $\mathcal{F}(\Delta_{G_{1}})=\{F_{1}\cup \{x_{2}\},...,F_{r}\cup \{x_{2}\}, H_{1}\cup \{x_{3},x_{5}\},...,H_{k}\cup \{x_{3},x_{5}\}\}$. Furthermore, $F_{1}\cup \{x_{2}\},...,F_{r}\cup \{x_{2}\}$ and $H_{1}\cup \{x_{3},x_{5}\},...,H_{k}\cup \{x_{3},x_{5}\}$ are shellings. Now, $x_{3}\in (H_{j}\cup \{x_{3},x_{5}\}) \setminus (F_{i}\cup \{x_{2}\})$ and $H_{j}$ is a stable set of $G$ without vertices of $C$. So, $H_{j}\cup \{x_{2},x_{5}\}$ is a maximal stable set of $G_{1}$ since  $N_{G}(x_{2},x_{5})=V(C)$ and $\{x_{2},x_{5}\}\notin E(G)$. Consequently, $H_{j}\cup \{x_{2},x_{5}\}=F_{l}\cup \{x_{2}\}$ for some $l\in \{1,...,r\}$ and $(H_{j}\cup \{x_{3},x_{5}\})\setminus (F_{l}\cup \{x_{2}\})=\{x_{3}\}$. Therefore, $G_{1}$ is a shellable graph. 

\vspace{0.2cm}

$\Leftarrow$) By Remark \ref{35}. \end{proof}


\begin{definition} A \textit{cut vertex} of a graph is one whose removal increases the number of connected components. A \textit{block} of a graph is a maximal subgraph without cut vertices. A connected graph without cut vertices with at least three vertices is called 2-connected graph.  \end{definition} 


In the following result $P$ is a property closed under c-minors.


\begin{theorem} \label{5} Let $G$ be a graph without 3-cycles and 5-cycles with a $2$-connected block $B$. If $G$ satisfies the property $P$ and $B$ does not satisfy $P$, then there exists $x\in D_1(B)$ such that \rm deg$_G(x)=1$ 
\end{theorem}

\begin{proof}
By contradiction, we assume that if $x\in D_{1}(B)$, then $\vert N_G(x) \vert >1$. Thus, there exist $a,b \in N_G(x)$ with $a\neq b$. We can suppose that $a\in V(B)$. If $b \in V(B)$, then $G[\{x\}\cup V(B)]$ is $2$-connected. But $B\subsetneq G[\{x\}\cup V(B)]$. This is a contradiction since $B$ is a block. Consequently, $V(B)\cap N_{G}(x)=\{a\}$. Now, we suppose that $b \in D_1(B)$. Since there is no 3-cycle in $G$, then $a\notin N_{G}(b)$. Hence, there exists $c \in N_G(b) \cap V(B)$ such that $c \neq a$. This implies $G[\{x,b\}\cup V(B)]$ is $2$-connected. But $B\subsetneq G[\{x,b\}\cup V(B)]$, a contradiction. Then $D_1(B)\cap N_G(x)=\emptyset$. Thus, $N_G(x)\cap (V(B) \cup D_1(B))=\{a\}$ and $b\in D_{2}(B)$. Now, if $D_1(B)=\{x_1,\ldots,x_r\}$, then there exists an $a_i$ such that $V(B)\cap N_G(x_i)=\{a_i\}$. Also, there exists $b_i$ such that  $b_i \in N_G(x_i)\cap D_2(B)$. We can suppose that $L=\{b_1,\ldots,b_s\}=\{b_1,\ldots,b_r\}$ with $b_i\neq b_j$ for $1\leq i<j\leq s$. We will prove that $L$ is a stable set. Suppose that $\{b_i, b_j\}\in E(G)$, if $a_i=a_j$, then $(a_i,x_i,b_i,b_j,x_j,a_i)$ is a 5-cycle in $G$, this is a contradiction. Consequently $a_i \neq a_j$ and the induced subgraph $G[\{x_i,b_i,b_j,x_j\}\cup V(B)]$ is $2$-connected. But $B$ is a block, then $\{b_i, b_j\}\notin E(G)$. Therefore, $L$ is a stable set. Furthermore, $G'=G\setminus N_G[L]$ is a c-minor of $G$, implying that $G'$ satisfies the property $P$. Since $D_1(B)\subset N_G(L)$, we have that $B$ is a connected component of $G'$. But, $B$ does not satisfy $P$. This is a contradiction since each connected component of $G$ is a c-minor. Therefore, there exists a free vertex in $D_1 (B)$. \end{proof} 


\begin{corollary} \label{3} Let $G$ be a graph without 3-cycles and 5-cycles and $B$ a $2$-connec\-ted block. If $G$ is shellable (unmixed, Cohen-Macaulay, sequentially Cohen-Ma\-cau\-lay or vertex decomposable) and  $B$ is not shellable (unmixed, Cohen - Macaulay, sequentially Cohen-Macaulay or vertex decomposable), then there exists $x\in D_1(B)$ such that $\deg_G(x)=1$. 
\end{corollary}

\begin{proof}
From Remark \ref{27}, Remark \ref{27-1} and Theorem \ref{5}.  \end{proof}


\begin{corollary} \label{20} Let $G$ be a bipartite graph and $B$ a 2-connected block. If $G$ is shellable, then there exists $x\in D_{1}(B)$ such that $\deg_{G}(x)=1$.  \end{corollary}

\begin{proof}
Since $G$ is bipartite, then $B$ is bipartite. If $H$ is a shellable bipartite graph, then $H$ has a free vertex (see \cite{VT}, Lemma 2.8), and so $H$ is not 2-connected. Hence, $B$ is not shellable. Therefore, by Corollary \ref{3}, there exists $x\in D_{1}(B)$ such that deg$_{G}(x)=1$. \end{proof}


\begin{lemma} \label{15} Let $G$  be a graph without 3-cycles and 5-cycles. If $G$ is vertex decomposable, then $G$ has a free vertex.
\end{lemma}

\begin{proof}
Since $G$ is vertex decomposable, then there is a shedding vertex $x$. Furthermore, there are no 5-cycles in $G$. Hence, by Theorem \ref{ext}, there exists $y\in N_{G}(x)$ such that $N_{G}[y]\subseteq N_{G}[x]$. If $z\in N_{G}(y)\setminus x$, then $(x,y,z)$ is a 3-cycle. This is a contradiction. Therefore, $N_{G}(y)=\{x\}$, implying that $y$ is a free vertex. \end{proof}
  

\begin{theorem} Let $G$  be a graph without 3-cycles and 5-cycles. $G$ is vertex decomposable if and only if there exists a free vertex $x$ with $N_{G}(x)=\{y\}$ such that $G_{1}=G\setminus N_{G}[x]$ and $G_{2}=G\setminus N_{G}[y]$ are vertex decomposable.  
\end{theorem} 

\begin{proof}
$\Rightarrow$) By Lemma \ref{15} there exists a free vertex $x$. Furthermore, by Remark \ref{27-1}, $G_{1}$ and $G_{2}$ are vertex decomposable.  

\vspace{0.2cm}

$\Leftarrow$) By Remark \ref{25}, $y$ is a shedding vertex. Moreover, $G\setminus y=G_{1}\cup \{x\}$. Furthermore, since $G_{1}$ is vertex decomposable, then $G\setminus y$ is also it. Therefore, $G$ is vertex decomposable, since $G_{2}$ is vertex decomposable. \end{proof}
 

\begin{corollary} \label{14} If $G$ is a 2-connected graph without 3-cycles and 5-cycles, then $G$ is not a vertex decomposable.
\end{corollary}

\begin{proof} Since $G$ is 2-connected, then $G$ does not have a free vertex. Therefore, by Lemma \ref{15}, $G$ is not vertex decomposable. \end{proof}


\begin{theorem} Let $G$ be a vertex decomposable graph without 3-cycles and 5-cycles. If $B$ is a 2-connected block of $G$, then $D_{1}(B)$ has a free vertex.
\end{theorem}

\begin{proof}
By Corollary \ref{14}, $B$ is not vertex decomposable. Therefore, by Theorem \ref{5}, $D_{1}(B)$ has a free vertex. \end{proof} 
 
\begin{definition} Let $G_{1},G_{2}$ be graphs. If $K=G_{1}\cap G_{2}$ is a complete graph with $|V(K)|=k$, then $G=G_{1}\cup G_{2}$ is called the \textit{k-clique-sum} (or clique-sum) of $G_{1}$ and $G_{2}$ in $K$.
\end{definition} 


\begin{corollary} If $G$ is the 2-clique-sum of the cycles $C_{1}$ and $C_{2}$ with $\vert V(C_{1}) \vert = r_{1}\leq r_{2}=\vert V(C_{2})\vert$, then $G$ is vertex decomposable if and only if $r_{1}=3$ or $r_{1}=r_{2}=5$.
\end{corollary}

\begin{proof}
$\Leftarrow$) First, we suppose that $r_{1}=3$. Consequently, we can assume $C_{1}=(x_{1},x_{2},x_{3})$ and $x_{2},x_{3}\in V(C_{1})\cap V(C_{2})$. Thus, $x_{1}$ is a simplicial vertex. Hence, by Remark \ref{25}, $x_{2}$ is a shedding vertex. Furthermore, $G\setminus x_{2}$ and $G\setminus N_{G}[x_{2}]$ are trees. Consequently, by Remark \ref{29}, $G\setminus x_{2}$ and $G\setminus N_{G}[x_{2}]$ are vertex decomposable graphs. Therefore, $G$ is vertex decomposable. 

\vspace{0.2cm}

Now, we assume that $r_{1}=r_{2}=5$ with $C_{1}=(x_{1},x_{2},x_{3},x_{4},x_{5})$ and $C_{2}=(y_{1},x_{2},x_{3},y_{4},$ $y_{5})$. We take a stable set $S$ in $G\setminus N_{G}[x_{5}]$. If $x_{2}\in S$, then $S\cup \{x_{4}\}$ is a stable set in $G_{1}=G\setminus x_{5}$. If  $x_{2}\notin S$, then  $S\cup \{x_{1}\}$ is a stable set in $G_1$. Consequently, by Lemma \ref{4}, $x_{5}$ is a shedding vertex.  Since $x_{2}$ is a neighbor of a free vertex in $G_{1}$, then $x_{2}$ is a shedding vertex in $G_{1}$. Furthermore, since $G_{1}\setminus x_{2}$ and $G_{1}\setminus N_{G_{1}}[x_{2}]$ are forests, then they are vertex decomposable graphs, by Remark \ref{29}. Thus, $G_{1}$ is vertex decomposable. Snce $G\setminus N_{G}[x_{5}]=C_{2}$, it is vertex decomposable by Remark \ref{29}. Therefore, $G$ is vertex decomposable. 

\vspace{0.2cm}

$\Rightarrow$) By Corollary \ref{14}, we have that $\{r_{1},r_{2}\}\cap \{3,5\}\neq\emptyset$. We suppose $r_{1}\neq 3$. So $r_{1}=5$ or $r_{2}=5$. Consequently, we can assume that  $\{C_{1},C_{2}\}=\{C,C'\}$ where $C=(x_{1},x_{2},x_{3},x_{4},x_{5})$ and $x_{2},x_{3}\in V(C)\cap V(C')$. Thus, $G\setminus N_{G}[x_{5}]=C'$ is vertex decomposable. Hence, from Remark \ref{29}, $\vert V(C')\vert\in \{3,5\} $. But $r_{1}\neq 3$,  then $\vert V(C')\vert=5$ and $r_{1}=r_{2}=5$. Therefore, $r_{1}=3$ or $r_{1}=r_{2}=5$. \end{proof} 


\begin{lemma} \label{16} Let $G$ be a 2-connected graph with girth at least 11. Then $G$ is not shellable. 
\end{lemma}

\begin{proof}
Since $G$ is 2-connected, then $G$ is not a forest. Consequently, if $r$ is the girth of $G$, then there exists a cycle $C=(x_{1},x_{2},...,x_{r})$. If $G=C$, then $G$ is not shellable. Hence, $G\neq C$ implying $D_{1}(C)\neq \emptyset$. We take $y\in D_{1}(C)$, without loss of generality we can assume that $\{x_{1},y\}\in E(G)$. If $\{x_{i},y\}\in E(G)$ for some $i\in \{2,...,r\}$, then we take the cycles $C_{1}=(y,x_{1},x_{2},...,x_{i})$ and $C_{2}=(y,x_{1},x_{r},x_{r-1},...,x_{i})$. Thus, $\vert V(C_{1})\vert =i+1$ and $\vert V(C_{2})\vert = r-i+3$. Since $r$ is the girth of $G$, then $i+1\geq r$ and $r-i+3\geq r$. Consequently, $3\geq i$ implies $4\geq r$. But $r\geq 11$, this is a contradiction. This implies that $\vert N_{G}(y)\cap V(C)\vert = 1$. Now, we suppose that there exist $y_{1},y_{2}\in D_{1}(C)$ such that $\{y_{1},y_{2}\}\in E(G)$. We can assume that $\{x_{1},y_{1}\}, \{x_{i},y_{2}\}\in E(G)$. Since $r\geq 11$, then there are no 3-cycles in $G$. In particular, $x_{1}\neq x_{i}$. Now, we take the cycles $C'=(y_{1},x_{1},...,x_{i},y_{2})$ and $C''=(y_{1},x_{1},x_{r},x_{r-1},...,x_{i},y_{2})$. So, $\vert V(C')\vert =i+2$ and $\vert V(C'')\vert = r-i+4$. Since $r$ is the girth, we have that $i+2\geq r$ and $r-i+4\geq r$. Hence, $4\geq i$ and $6\geq r$, this is a contradiction. Then $D_{1}(C)$ is a stable set. Now, since $G$ is 2-connected, then for each $y\in D_{1}(C)$ there exists $z\in N_{G}(y)\cap D_{2}(C)$. If there exist $z_{1},z_{2}\in D_{2}(C)$ such that $\{z_{1},z_{2}\}\in E(G)$, then there exist $y_{1},y_{j}\in D_{1}(C)$ such that $\{z_{1},y_{1}\}, \{z_{2},y_{j}\}\in E(G)$. Since there are no 3-cycles in $G$, we have that $y_{1}\neq y_{j}$. We can assume that $\{x_{1},y_{1}\}, \{x_{i},y_{j}\}\in E(G)$. Since there are no 5-cycles, then $i\neq 1$. Consequently, there exist cycles $C_{1}'=(x_{1},...,x_{i},y_{j},z_{2},z_{1},y_{1})$ and $C_{2}'=(x_{i},...,x_{r},x_{1},y_{1},z_{1},z_{2},y_{j})$. This implies $r\leq \vert V(C_{1}')\vert =i+4$ and $r\leq \vert V(C_{2}')\vert =r-i+6$. Hence, $i\leq 6$ and $r\leq 10$, this is a contradiction. Then $D_{2}(C)$ is a stable set. Furthermore, $C$ is a connected component of $G\setminus N_{G}[D_{2}(C)]$. But $C$ is not shellable, therefore $G$ is not shellable, from Remark \ref{27-1}. \end{proof}


\begin{theorem} If $G$ has girth at least 11, then $G$ is shellable if and only if there exists $x\in V(G)$ with $N_{G}(x)=\{y\}$ such that $G\setminus N_{G}[x]$ and $G\setminus N_{G}[y]$ are shellable.    
\end{theorem}

\begin{proof}
$\Leftarrow$) By (\cite{VT}, Theorem 2.9). 

\vspace{0.2cm}

$\Rightarrow$) By Remark \ref{27-1}, shellability is closed under c-minors. Consequently, it is only necessary to prove that $G$ has a free vertex. If every block of $G$ is an edge or a vertex, then $G$ is a forest and there exists $x\in V(G)$ with deg$_{G}(x)=1$. Hence, we can assume that there exists a 2-connected block $B$ of $G$. The girth of $B$ is at least 11, since $B$ is an induced subgraph of $G$. Thus, by Lemma \ref{16}, $B$  is not shellable. Therefore, by Theorem \ref{5}, there exists $x\in D_{1}(B)$ such that $\deg_{G}(x)=1$. \end{proof} 










%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The authors are grateful to the referees whose suggestions improved the presentation of this paper.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{Biermann} J.~Biermann, C. A. Francisco, and  H. T$\grave{{\rm a}}$i H$\grave{{\rm a}}$, A. Van Tuyl.  \newblock Partial coloring, vertex decomposability and sequentially Cohen-Macaulay simplicial complexes.  \newblock {\em J. Commut. Algebra}, 7(3):337--352, 2015.

\bibitem{BC} T. Biyiko$\check{{\rm g}}$lu and Y. Civan. \newblock  Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity. \newblock {\em Electron. J. Combin.}, 21(1), 2014.

\bibitem{BH} A. Bruns and J. Herzog. \newblock {\em Cohen-Macaulay Ring}. \newblock  Cambridge University Press, Cambridge, 1998.

\bibitem {CC} I. D. Castrill\'on and R. Cruz. \newblock Escalonabilidad de grafos e hipergrafos simples que contienen v\'ertices simpliciales. \newblock {\em Matem\'aticas: Ense\~nanza Universitaria}, XX(1):69--80, 2012.

\bibitem{half} M. Crupi, G. Rinaldo, and N. Terai. \newblock Cohen-Macaulay edge ideal whose height is half of the number of vertices. \newblock {\em Nagoya Math. J.}, 201:117--131, 2011.

\bibitem{Doch} A. Dochtermann and A. Engstr$\ddot{{\rm o}}$m. \newblock Algebraic properties of edge ideals via combinatorial topology. \newblock {\em Electron. J. Combin.}, 16(2), 2009.

\bibitem{Villa5} M. Estrada and R. H. Villarreal. \newblock Cohen-Macaulay bipartite graphs. \newblock {\em  Arch. Math.}, 68(2):124--128, 1997.

\bibitem{Finbow}  A. Finbow, B. Hartnell,and R. J. Nowakowski. \newblock A characterization of well co\-ve\-red graphs of girth 5 or greater. \newblock {\em J. Combin. Theory Ser. B}, 57(1):44--68, 1993.

\bibitem{Chris} C. A. Francisco and A. Van Tuyl. \newblock Sequentially Cohen-Macaulay edge ideals. \newblock {\em Proc. Amer. Math. Soc. (electronic)}, 135(8):2327--2337, 2007.

\bibitem{GV} I. Gitler and C. E. Valencia. \newblock On bounds for some graph invariants. \newblock {\em Bol. Soc. Mat. Mexicana}, 16(2):73--94, 2010.

\bibitem{HH} J. Herzog and T. Hibi. \newblock Distributive lattices, bipartite graphs and Alexander duality. \newblock {\em J. Algebraic Combin.}, 22:289--302, 2005.

\bibitem{ON} D. T. Hoang, N. C. Minh, T. N Trung. \newblock Cohen-Macaulay graphs with large girth. \newblock {\em J. Algebra Appl.}, 14(7), 2015.

\bibitem{MM} M. Mahmoudi, A. Mousivand, M. Crupi, G. Rinaldo, N. Terai, and S. Yassemi. \newblock Vertex decomposability and regularity of very well-covered graphs. \newblock {\em  J. Pure Appl. Algebra}, 215(10):2473--2480, 2011.


\bibitem{MR} S. Morey, E. Reyes, and R. H. Villarreal. \newblock Cohen-Macaulay, shellable and unmixed clutters with perfect matching of K$\ddot{{\rm o}}$nig type. \newblock {\em J. Pure Appl. Algebra}, 212(7):1770--1786, 2008.

\bibitem{Ra} G. Ravindra. \newblock Well-covered graphs. \newblock {\em J. Combin. Inform. System Sci.} 2(1):20--21, 1977.

\bibitem{Stanley} R. P. Stanley.  \newblock {\em  Combinatorics and Commutative Algebra}. \newblock Second edition, Progress in Mathematics 41. Birkh$\ddot{{\rm a}}$user Boston, Inc., Boston, MA. 1996.

\bibitem{V} A. Van Tuyl. \newblock Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity. \newblock {\em Arch. Math.}, 93:451-459, 2009.

\bibitem{VT} A. Van Tuyl, and R. H. Villarreal. \newblock Shellable graphs and sequentially Cohen-Macaulay bipartite graphs. \newblock {\em  J. Combin. Theory Ser. A}, 115(5):799--814, 2008.

\bibitem{Villa3} R. H. Villarreal. \newblock Unmixed bipartite graphs. \newblock {\em  Rev. Colombiana Mat.}, 41(2):393--395, 2007.

\bibitem{Villa} R. H. Villarreal. \newblock {\em Monomial Algebras}. \newblock  Second edition,  Monographs and Research Notes in Mathematics, Chapman \& Hall/CRC. 2015.

\bibitem{wachs} M. L Wachs. \newblock Obstructions to shellability. \newblock {\em  Discrete Comput. Geom.}, 22(1):95--103, 1999.

\bibitem{RW} R. Woodroofe. \newblock Vertex decomposable graphs and obstructions to shellability. \newblock {\em  Proc. Amer. Math. Soc.}, 137:3235-3246, 2009.




\end{thebibliography}

\end{document}
