% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.39}{23(2)}{2016} % 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}{May 10, 2016}{May 27, 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\dots" or "we study\dots" should be kept to a minimum % in favor of "we prove that\dots" or "we show that\dots". 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},\dots,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},\dots,x_{n}\}$ and edge set $E(G)$. Let $R=k[x_{1},\dots,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 \varnothing$ 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},\dots,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},\dots,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, motivate 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]=\varnothing$, 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},\dots,y_{k}\}$. If $G$ does not satisfy (a), then there is \[\{z_{1},\dots,z_{k}\} \subseteq V(G)\setminus N_{G}[x]\] such that $\{y_{i},z_{i}\}\in E(G)$ for $i\in\{1,\dots,k\}$. We denote by $L=\{z_{1},\dots,z_{q}\}=\{z_{1},\dots,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},\dots,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},\dots,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 \varnothing$, then $G'$ has a perfect matching $e_{1},\dots,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},\dots,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},\dots,y_{s}$ are free vertices in $N_{G}(x)$. Hence, $G_{1}=G\setminus N_{G}[y_{1},\dots,y_{s}]=G\setminus \{x,y_{1},\dots,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},\dots,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},\dots,F_{s}$ such that for all $1\leq ij_{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},\dots,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},\dots,x_{j_r}\}$ with $j_{1}< \cdots 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},\dots,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},\dots,F_{l},G_{2},\dots,G_{k}$ where $F_{1},\dots,F_{l}$ are the connected components of $G_{1}\setminus N_{G_1}[x]$. By induction hypothesis $G_{2},\dots,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,\dots,l\}$. By induction hypothesis, we have that $F_{i}$ has a perfect matching $M_{i}=\{e_{1}^{i},\dots,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},\dots,x_{s}\}$, $V(G)=V(H)\cup \{y_{1},\dots,y_{s}\}$ and $E(G)=E(H)\cup W(H)$ where $W(H)=\{\{x_{1},y_{1}\},\dots,\{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}\},\dots,\{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},\dots,x_{n}]$. Therefore, $G$ is a whisker graph with $W(H)=\{\{x_{1},y_{1}\},\dots,\{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},\dots,F_{k}$ and $G_{1},\dots,G_{q}$, respectively, then $G$ is shellable with shelling $F_{1},\dots,F_{k},G_{1}\cup\{v\},\dots,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},\dots,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},\dots,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}\},\dots,F_{r}\cup \{x_{2}\}, H_{1}\cup \{x_{3},x_{5}\},\dots,H_{k}\cup \{x_{3},x_{5}\}\}$. Furthermore, $F_{1}\cup \{x_{2}\},\dots,F_{r}\cup \{x_{2}\}$ and $H_{1}\cup \{x_{3},x_{5}\},\dots,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,\dots,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)=\varnothing$. 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