\section{Introduction}

Milnor \cite{milnor}
observed that the mod 2 Steenrod algebra $\mathcal{A}$ forms a Hopf algebra with
commutative diagonal determined by
\begin{equation}
\Delta \mathrm{Sq}^n=\sum_i\mathrm{Sq}^i\otimes\mathrm{Sq}^{n-i}\,.
\end{equation}
This allowed him to interpret the Cartan formula
as the assertion that the cohomology of a space forms a module-algebra
over $\mathcal{A}$. The anti-automorphism $\chi$ in the Hopf algebra structure,
defined inductively by
\begin{equation}
\chi\mathrm{Sq}^0=\mathrm{Sq}^0\quad,\quad
\sum_i\mathrm{Sq}^i\chi\mathrm{Sq}^{n-i}=0\quad\hbox{for}\quad n>0\,,
\label{def-chi}
\end{equation}
has a topological interpretation too: If $K$ is a finite complex then
the homology of the Spanier-Whitehead dual $DK_+$ of $K_+$ is canonically
isomorphic to the cohomology of $K$. Under this isomorphism the left
action by $\theta\in\mathcal{A}$ on $H^*(K)$ corresponds to the right action of
$\chi\theta\in\mathcal{A}$ on $H_*(DK_+)$.

In 1974 Davis \cite{davis}
proved that sometimes much more efficient ways exist to
compute $\chi\mathrm{Sq}^n$:
\begin{equation}
\chi\mathrm{Sq}^{2^r-1}=\mathrm{Sq}^{2^{r-1}}\chi\mathrm{Sq}^{2^{r-1}-1}
\label{davis-one}
\end{equation}
\begin{equation}
\chi\mathrm{Sq}^{2^r-r-1}=\mathrm{Sq}^{2^{r-1}-1}\chi\mathrm{Sq}^{2^{r-1}-r}
+\mathrm{Sq}^{2^{r-1}}\chi\mathrm{Sq}^{2^{r-1}-r-1}
\label{davis-two}
\end{equation}
Similarly, Straffin \cite{straffin} proved that if $r\geq0$ and $b\geq2$ then
\begin{equation}
\sum_i\mathrm{Sq}^{2^ri}\chi\mathrm{Sq}^{2^r(b-i)}=0\,.
\end{equation}
Both authors give analogous identities among reduced powers and their
images under $\chi$ at an odd prime as well.

Barratt and Miller \cite{barratt-miller} found a general family of identities
which includes all these as special cases. We state it for the general prime.
When $p=2$, $P^n$ denotes $\mathrm{Sq}^n$. Let $\alpha(n)$ denote the sum of the
$p$-adic digits of $n$.

\begin{theorem} \cite{barratt-miller,crabb-crossley-hubbuck}
For any integer $k$ and any integer $l\geq0$ such that $pl-\alpha(l)<(p-1)n$
\begin{equation}
\sum_i\binom{k-i}{l}P^i\chi P^{n-i}=0\,.
\label{bm}
\end{equation}
\label{th-bm}
\end{theorem}

The defining relations occur with $l=0$.
Davis's formulas (for $p=2$) are the cases in which
$(n,l,k)=(2^r-1,2^{r-1}-1,2^r-1)$ or $(n,l,k)=(2^r-r-1,2^{r-1}-2,2^r-2)$.
Straffin's identities (for $p=2$) occur as $(n,l,k)=(2^rb,2^r-1,2^rb)$.

Since $\binom{(k+1)-i}{l}-\binom{k-i}{l}=\binom{k-i}{l-1}$,
the cases $(l,k+1)$ and $(l,k)$ of  (\ref{bm}) imply it for
$(l-1,k)$. Thus the relations for
\begin{equation}
l=l(n)=\max\{j:pj-\alpha(j)<(p-1)n\}
\label{ln}
\end{equation}
imply all the rest. When $p=2$,
$l(2^r-1)=2^{r-1}-1$ and $l(2^r-r-1)=2^{r-1}-2$,
so Davis's relations are among these basic relations.

Two questions now arise. To express them uniformly in the prime, let
$\mathcal{P}$ denote the algebra of Steenrod reduced powers (which is the full
Steenrod algebra when $p=2$), but assign $P^n$ degree $n$. It is natural to
ask:  \\
-- Are there yet other linear relations among the $n+1$
elements $P^i\chi P^{n-i}$ in $\mathcal{P}^{n}$? \\
-- What is a minimal spanning set for
\[
V_n=\mathrm{Span}\{P^i\chi P^{n-i}:0\leq i\leq n\}\subseteq\mathcal{P}^n
\]
We answer these questions in
Theorem \ref{main-theorem} below.

Write $e_i,0\leq i\leq n$, for the $i$th standard basis vector in
$\mathbb{F}_p^{n+1}$.

\begin{proposition}
For any integers $l,m,n$, with $0\leq l\leq n$,
\begin{equation}
\left\{\sum_i\binom{k-i}{l}e_i:m\leq k\leq m+l\right\}
\label{basis}
\end{equation}
is linear independent in $\mathbb{F}_p^{n+1}$.
\label{prop-basis}
\end{proposition}

\begin{proposition}
The set
\begin{equation}
\left\{P^i\chi P^{n-i}:l(n)+1\leq i\leq n\right\}
\label{basis2}
\end{equation}
is linearly independent in $\mathcal{P}^n$.
\label{prop-basis2}
\end{proposition}

Define a linear map
\begin{equation}
\mu:\mathbb{F}_p^{n+1}\rightarrow\mathcal{P}^n\quad,\quad
\mu e_i=P^i\chi P^{n-i}
\end{equation}
Theorem \ref{th-bm} implies that if $l=l(n)$ the elements in (\ref{basis})
lie in $\mathrm{ker}\,\mu$, so Propositions \ref{prop-basis} and \ref{prop-basis2}
imply that (\ref{basis}) with $l=l(n)$ is a basis for $\mathrm{ker}\,\mu$ and that
(\ref{basis2}) is a basis for $V_n\subseteq\mathcal{P}^n$. Thus:

\begin{theorem} Any $l+1$ consecutive relations from the set
{\rm(\ref{bm})} with $l=l(n)$ form a basis of relations among the elements of
$\{P^i\chi P^{n-i}:0\leq i\leq n\}$. The set
$\{P^i\chi P^{n-i}:l(n)+1\leq i\leq n\}$ is a basis for $V_n$.
\label{main-theorem}
\end{theorem}

\noindent
{\bf Acknowledgement.} We thank Richard Stanley for the slick proof of
Proposition \ref{prop-basis}.

\section{Independence of the relations}

We wish to show that (\ref{basis}) is a linearly independent set.
Regard elements of $\mathbb{F}_p^{n+1}$ as column vectors, and arrange
the $l+1$ vectors in (\ref{basis}) as columns in a matrix,
which we claim is of rank
$l+1$. The top square portion is the mod $p$ reduction of the
$(l+1)\times(l+1)$ integral Toeplitz matrix $A_l(m)$ with $(i,j)$th entry
\[
\binom{m+j-i}{l}\quad,\quad 0\leq i,j\leq l
\]

\begin{lemma} $\det A_l(m)=1$.
\end{lemma}

\noindent
{\em Proof.} By induction on $m$. Since $\binom{-1}{l}=(-1)^l$ and
$\binom{-1+j}{l}=0$ for $0<j\leq l$, $A_l(-1)$ is lower triangular
with determinant $((-1)^l)^{l+1}=1$. Now we note the identity
\[
BA_l(m)=A_l(m+1)
\]
where
\[
B=\left[\begin{array}{ccccc}
\binom{l+1}{1} & -\binom{l+1}{2} & \cdots & (-1)^{l-1}\binom{l+1}{l} &
(-1)^l\binom{l+1}{l+1} \\
1 & 0 & \cdots & 0 & 0 \\
0 & 1 & \cdots & 0 & 0\\
\vdots & \vdots & & \vdots & \vdots \\
0 & 0 & \cdots & 1 & 0
\end{array}\right].
\]
The matrix identity is an expression of the binomial identity
\begin{equation}
\sum_k(-1)^k\binom{l+1}{k}\binom{n-k}{l}=0
\label{bin1}
\end{equation}
(taking $n=m+1-j$ and $k=j+1$). Since $\det B=1$, the result follows
for all $m\in\mathbb{Z}$. $\Box$

For completeness, we note that (\ref{bin1}) is the case $m=l+1$ of:

\begin{lemma}
$\displaystyle{\sum_k(-1)^k\binom{m}{k}\binom{n-k}{l}=\binom{n-m}{l-m}}$.
\end{lemma}

\noindent
{\em Proof.} The defining identity for binomial coefficients implies the case
$m=1$, and also that both sides satisfy the recursion
$C(l,m,n)-C(l,m,n-1)=C(l,m+1,n)$. $\Box$

\section{Independence of the operations}

We will prove Proposition \ref{prop-basis2} by studying how
$P^i\chi P^{n-i}$ pairs against elements in $\mathcal P_*$, the dual of the
Hopf algebra of Steenrod reduced powers. According to Milnor \cite{milnor},
with our grading conventions
\[
\mathcal{P}_*=\mathbb{F}_p[\xi_1,\xi_2,\ldots] \quad,\quad
|\xi_j|=\frac{p^j-1}{p-1}\,,
\]
and
\begin{equation}
\Delta\xi_k=\sum_{i+j=k}\xi_i^{2^j}\otimes\xi_j\,.
\label{milnor-diagonal}
\end{equation}
For a finitely nonzero sequence of nonnegative integers
$R=(r_1,r_2,\ldots)$ write $\xi^R=\xi_1^{r_1}\xi_2^{r_2}\cdots$ and let
$\lVert R\rVert=r_1+pr_2+p^2r_3+\cdots$ and
\[
|R|=|\xi^R|=
r_1+\left(\frac{p^2-1}{p-1}\right)r_2+\left(\frac{p^3-1}{p-1}\right)
r_3+\cdots\,.
\]
The following clearly implies Proposition \ref{prop-basis2}.

\begin{proposition} For any integer $n>0$ there exist sequences
$R_{n,j}$, $0\leq j\leq n-l(n)-1$, such that $|R_{n,j}|=n$ and
\[
\langle P^i\chi P^{n-i},\xi^{R_{n,j}}\rangle=\left\{
\begin{array}{cll}
\pm1 & \hbox{for} & i=n-j \\
0 & \hbox{for} & i>n-j\,.
\end{array}\right.
\]
\label{basis3}
\end{proposition}

\noindent
The starting point in proving this is the following result of Milnor
\cite{milnor}.

\begin{lemma} [\cite{milnor}, Lemma 10]
$\langle\chi P^n,\xi^R\rangle\neq0$ for all sequences $R$ with $|R|=n$.
\end{lemma}

In the basis of $\mathcal{P}$ dual to the monomial basis of $\mathcal{P}_*$, the element
corresponding to $\xi_1^i$ is $P^i$. Since the diagonal in $\mathcal{P}_*$ is dual
to the product in $\mathcal{P}$, it follows from (\ref{milnor-diagonal}) that
\[
\langle P^i\chi P^{n-i},\xi^R\rangle=\left\{
\begin{array}{cll}
\pm1 & \hbox{for} & i=\lVert R\rVert\\
0 & \hbox{for} & i>\lVert R\rVert\,.
\end{array}
\right.
\]

So we wish to construct sequences $R_{n,j}$, for $l(n)+1\leq j\leq n$,
such that $|R_{n,j}|=n$ and $\lVert R_{n,j}\rVert=j$. We deal first with the
case $j=l(n)+1$.

\begin{proposition} For any $n\geq0$ there is a sequence
$M=(m_1,m_2,\ldots)$ such that \\
{\rm(1)} $|M|=n$, \\
{\rm(2)} $0\leq m_i\leq p$ for all $i$, and \\
{\rm(3)} If $m_j=p$ then $m_i=0$ for all $i<j$. \\
For any such sequence, $\lVert M\rVert=l(n)+1$.
\label{M}
\end{proposition}

\noindent
{\em Proof.} Give the set of sequences of dimension $n$
the right-lexicographic order.
We claim that the maximal sequence satisfies the hypotheses.

Suppose that $R=(r_1,r_2,\ldots)$ does not satisfy the hypotheses.
If $r_1>p$ then the sequence $(r_1-(p+1),r_2+1,r_3,\ldots)$ is larger.
If $r_j>p$, with $j>1$, then the sequence
$(r_1,\ldots,r_{j-2},r_{j-1}+p,r_j-(p+1),r_{j+1}+1,r_{k+2},\ldots)$ is larger.
This proves (2).
To prove (3), suppose that $r_j=p$ with $j>1$, and suppose that some
earlier entry is nonzero. Let $i=\min\{k:r_k>0\}$. If $i=1$, then the
sequence $(r_1-1,r_2,\ldots,r_{j-1},0,r_{j+1}+1,r_{j+2},\ldots)$ is larger.
If $i>1$, then $S$ with $s_k=0$ for $k<i-1$ and $i\leq k\leq j$,
$s_{i-1}=p$, $s_{j+1}=r_{j+1}+1$, and $s_k=r_k$ for $k>j+1$, is larger.

Let $M$ be a sequence satisfying (1)--(3), and write $l=\lVert M\rVert-1$.
To see that $l=l(n)$  we must show that
\begin{equation}
p(l+1)-\alpha(l+1)\geq(p-1)n
\label{greater}
\end{equation}
and
\begin{equation}
pl-\alpha(l)<(p-1)n\,.
\label{less}
\end{equation}
The {\em excess} $e(R)$ is the sum of the entries in $R$, so that
$p\lVert R\rVert-e(R)=(p-1)|R|$.  The $p$-adic representation of a number
minimizes excess, so for any sequence $R$ we have
$e(R)\geq\alpha(\lVert R\rVert)$ and hence
$p\lVert R\rVert-\alpha(\lVert R\rVert)\geq(p-1)|R|$: so (\ref{greater})
holds for any sequence.

To see that (\ref{less}) holds for $M$, let
$j=\min\{i:m_i>0\}$, so that $(p-1)n=(p^j-1)m_j+(p^{j+1}-1)m_{j+1}+\cdots$ and
$l+1=p^{j-1}m_j+p^jm_{j+1}+\cdots$. The hypotheses imply that
$l$ has $p$-adic expansion
\[
(1+\cdots+p^{j-2})(p-1)+p^{j-1}(m_j-1)+p^jm_{j+1}+\cdots,
\]
so
\[
\alpha(l)=(j-1)(p-1)+(m_j-1)+m_{j+1}+\cdots
\]
from which we deduce
\[
pl-\alpha(l)=(p-1)(n-j)<(p-1)n\,.
\]

\begin{corollary}
The function $l(n)$ is weakly increasing.
\end{corollary}

\noindent
{\em Proof.}
Let $M$ be a sequence satisfying the conditions of Proposition \ref{M},
and note that the sequence $R=(1,0,0,\ldots)+M$ has $|R|=n+1$ and
$\lVert R\rVert=\lVert M\rVert+1=l(n)+2$. If $p$ does not occur in
$M$, then $R$ satisfies the hypotheses of the proposition (in degree $n+1$)
and hence $l(n)+1\leq l(n+1)+1$.
If $p$ does occur in $M$, then the moves described above will
lead to a sequence $M'$ satisfying the hypotheses. None of the moves
decrease $\lVert-\rVert$, so $l(n)+1\leq l(n+1)+1$. $\Box$

\begin{remark} {\rm Properties (1)--(3) in fact determine $M$ uniquely.}
\end{remark}

\noindent
{\em Proof of Proposition \ref{basis3}.} Define $R_{n,l(n)+1}$ to be a sequence
$M$ as in Proposition \ref{M}. Then inductively define
\[
R_{n,j}=(1,0,0,\ldots)+R_{n-1,j-1}\quad\hbox{for}\quad l(n)+1<j\leq n\,.
\]
This makes sense by monotonicity of $l(n)$, and the elements clearly
satisfy $|R_{n,j}|=n$ and $\lVert R_{n,j}\rVert=j$. This completes the
proof. $\Box$


\section{Introduction}
A graph G is said to be well-covered (or unmixed) if every maximal independent sets of vertices
have the same cardinality. These graphs were introduced by M.~D.~Plummer~\cite{16} in
1970. Although the recognition problem of well-covered graphs in general is
Co-NP-complete~(\cite{19}), it is characterized for certain classes of graphs. For instance,
claw-free well-covered graphs~\cite{22}, well-covered graphs which have girth at least~5~\cite{7},
(4-cycle, 5-cycle)-free~\cite{8} or chordal graphs~\cite{18}
 are all
recognizable in polynomial time. Excellent surveys of works on
well-covered graphs are given in Plummer~\cite{17} and Hartnell~\cite{10}.

Let $G$ be a graph with no loop and multiple edge. Denote the set of vertices of $G$ by $V(G)$ and the set
of edges by $E(G)$. A subset $A$ of $V(G)$ is called an independent set if there is no any edge between vertices of $A$. Denote the cardinality of the largest independent set in $G$ by $\alpha(G)$.
A subset $C$ of $V(G)$ is called a clique if any two vertices in $C$ are adjacent.

Let $A$ and $B$ be subsets of $V(G)$. We say $A$ dominates $B$ if for any vertex $v$ in $B$, $v$ is in $A$ or there is at least one vertex in $A$ adjacent to $v$. The set $A$ is called a vertex cover of $G$ if any edge of $G$ has at least one edge in $A$. A vertex cover is called minimal if any proper subset of it is not a vertex cover.

A subset of $E(G)$ is called a matching if there is not any common vertex in any two edges in this set.
A matching is called perfect matching if it covers all vertices of $G$.

Let $[n] = \{1,2,\ldots,n\}$. A (finite) simplicial complex $\Delta$ on $n$ vertices, is a collection of subsets of
$[n]$ such that the following conditions hold:\\
a) $\{i\}\in\Delta$ for each $i\in [n]$,\\
b) if $E\in\Delta$ and $F\subseteq E$, then $F\in\Delta$.\\
An element of $\Delta$ is called a face and a maximal face with respect to inclusion is called a facet.
The set of all facets is denoted by $\mathcal{F}(\Delta)$.  The dimension of a
face $F\in\Delta$ is defined to be $|F|-1$ and dimension of $\Delta$ is maximum of dimensions of its faces.
A simplicial complex is called pure if all of its facets have the same dimension. For more details on simplicial complexes see \cite{Stan}.

Let $G$ be a graph. The set of all independent sets of vertices of $G$ is a simplecial complex, because,
any single vertex is independent and any subset of an independent
set is again independent. We assume that the empty set is also an independent set. This simplicial complex is called independence complex of $G$ and is denoted by $\Delta_G$.  With the above definitions,
a graph $G$ is well-covered means that the complex $\Delta_G$ is pure.

Let $\Delta$ be a simplicial complex on the vertex set $[n]$. The
barycentric subdivision of $\Delta$, denoted by $\mbox{bs}(\Delta)$, is
a simplicial complex with vertex set consisting of all nonempty
faces of $\Delta$. A face in $\mbox{bs}(\Delta)$ consists of comparable vertices, that is, two vertices
lie in a face in $\mbox{bs}(\Delta)$ if one is a subset of the other. In other words,
facets of $\mbox{bs}(\Delta)$ are maximal chains of faces of
$\Delta$ considered as a poset with respect to inclusion order.

It is easy to see that the minimal non-faces of $\mbox{bs}(\Delta)$ are
subsets of $\Delta$ with exactly two non-comparable elements.
Therefore, $\mbox{bs}(\Delta)$ is an independence  complex of a graph.
In fact this graph is non-comparability graph of $\Delta$. Vertices of the graph are nonempty faces of $\Delta$ and two vertices are adjacent if their corresponding faces are not comparable.
This graph is denoted by $G(\Delta)$.

It is
known that the dimension (and many other invariants) of a simplicial
complex and its barycentric subdivision are equal (\cite{BW} and \cite{KW}). Specially a simplicial complex $\Delta$ is pure if and only if its barycentric subdivision is pure and it is equal to say that the graph $G(\Delta)$ is well-covered.

\section{Well-covered graphs with clique covers}

Let $\cal G$ be the class of graphs such that for each $G\in \cal G$ there are $k=\alpha(G)$ cliques in $G$ covering all its vertices. Let $G\in \cal G$ and $Q_1,\ldots,Q_k$ be cliques such that $V(Q_1)\cup\cdots\cup V(Q_k)=V(G)$. In this case, we may take $Q'_1=Q_1$, and for $i=2,\ldots,k$, $Q'_i$ the induced graph on the vertices $V(Q_i)\setminus (V(Q_1)\cup\cdots\cup V(Q_{i-1}))$. Then, $Q'_1,\ldots,Q'_k$ are $k$ disjoint cliques covering all vertices of $G$. We call such a set of cliques, a basic clique cover of the graph $G$. Therefore, any graph in the class $\cal G$ has a basic clique cover. Note that, $k=\alpha(G)$ is the smallest number which the graph $G$ may has a clique cover. It is not true that any graph has a basic clique cover. For example, a cycle of length 4 has a basic clique cover consisting of 2 cliques but a cycle of length 5 does not have any basic clique cover.

\begin{proposition}\label{class}
Let $\Delta$ be a simplicial complex. Then, $G(\Delta)$ is in the class $\cal G$. Moreover, $\Delta$ is pure if and only if $G(\Delta)$ is well-covered.
\end{proposition}

{\it Proof}. Note that any two faces in $\Delta$ with the same dimension are not comparable. Therefore, for each $i$,  $0\leq i\leq \dim(\Delta)$, if $\Delta(i)$ is the set of all faces of $\Delta$ with dimension $i$, then there are not any two comparable face in this set and the corresponding vertices in the graph $G(\Delta)$ make a clique. These cliques are disjoint and cover all vertices of $G(\Delta)$. In fact the set of these cliques is a basic clique cover of $G(\Delta)$. The last statement is clear. \hfill $\Box$

Now, we give some criteria equivalent to well-covered property of graphs in the class $\cal G$.

\begin{theorem}\label{main} Let $G$ be a graph in the class $\cal G$ with a basic clique cover $Q_1, \ldots, Q_k$. Then $G$ is well-covered  if and only if for each $i$, $1\leq i\leq k$, if $A\subseteq V(G)\setminus Q_i$ dominates $Q_i$, then $A$ is not an independent set.
\end{theorem}

{\it Proof.} Assume that $G$ is well-covered. Let $1\leq i\leq k$ be given and $A\subseteq V(G)\setminus Q_i$ be a dominating set of $Q_i$. If $A$ is independent, then there is a maximal independent set $B$ containing $A$. But, $B\cap Q_i=\varnothing$ because any vertex of $Q_i$ is adjacent to some vertices in $A\subseteq B$. In other hand, $B$ has at most one element in common with each $Q_j$, $j\neq i$. Therefore, $|B|<k$ which is a contradiction with well-coveredness of $G$.

Conversely, let $A$ be a maximal independent set. Then $|A\cap Q_i|\leq 1$ for each $1\leq i\leq k$ and $|A|\leq k$.
The claim follows if one shows
$|A|=k$. So, if one assume $|A\cap Q_i|=\varnothing$ for some $i$, then one can apply the assumption
and $A$ is not dominating for $Q_i$, which means that there exists a $v \in Q_i$
not adjacent to any vertex of $A$. By maximality of $A$, $v\in A$ and hence $|A\cap Q_i|=1$
which is a contradiction to the assumption. So, finally one get $|A\cap Q_i|=1$ and
the claim follows. \hfill $\Box$

\begin{proposition}\label{partite} Let $G$ be a $s$-partite well-covered graph such that all maximal cliques are of size $s$. Then all parts have the same cardinality and there is a perfect matching between each two parts.
\end{proposition}

{\it Proof.} Let the $s$ parts of $G$ be $V_1, \ldots, V_s$. Let $1\leq i\leq s$ and $v\in V_i$. Each vertex  belongs to some maximal clique and each maximal clique intersects each part in exactly one vertex. Therefore, the vertex $v$ is adjacent to some vertices in each part $V_j$, $1\leq j\leq s$, $j\neq i$. Then the part $V_i$ is a maximal independent set because for each vertex out of $V_i$, there is an edge connecting it to some vertex in $V_i$. The graph $G$ is well-covered therefore, cardinality of parts are the same.

Let $1\leq i < j\leq s$ be two given integers.
Let $A\subseteq V_i$ be a nonempty set and $N_j(A)$ be the set of all vertices in $V_j$ adjacent to some vertices in $A$. Suppose $|N_j(A)|< |A|$. There is no any edge between $A$ and $V_j\setminus N_j(A)$. Therefore, $A\cup (V_j\setminus N_j(A))$ is an  independent set and its size is strictly greater than size of $V_j$, which is a contradiction with well-coveredness of $G$. Therefore, $|N_j(A)| \geq |A|$ for each nonempty subset $A$ of $V_i$. Therefore, by Theorem of Hall~\cite{Hall}, there is a set of distinct representatives (SDR) for the set $\{N_j(\{v\}) : v\in V_i\}$, which is a perfect matching between $V_i$ and $V_j$. \hfill $\Box$

\paragraph{Example.} It is not true that in a well-covered graph $G$, there are $\alpha(G)$ maximal cliques covering $G$. For instance, consider any cycle $C_n$ for odd $n$. In this case, $\alpha(C_n)=\frac{n-1}{2}$ and any $\frac{n-1}{2}$ cliques, which are edges, can not cover all vertices. Also the above statement is not true in class of all well-covered $s$-partite graphs. For instance consider the following graph which is 3-partite, well-covered with maximal independent sets of size 2. But, there are no two maximal cliques covering $V(G)$.

$$
\unitlength=1cm
    \begin{picture}(-4,-1)(3,1.5)
     \put(0,0.5){\circle*{0.1}}
     \put(1,0){\circle*{0.1}}
     \put(2,0.5){\circle*{0.1}}
     \put(0,2){\circle*{0.1}}
     \put(1,1.5){\circle*{0.1}}
     \put(2,2){\circle*{0.1}}
     \put(0,0.5){\line(2,-1){1}}
     \put(0,0.5){\line(1,0){2}}
     \put(0,0.5){\line(1,1){1}}
     \put(0,0.5){\line(4,3){2}}
     \put(1,0){\line(2,1){1}}
     \put(1,0){\line(1,2){1}}
     \put(2,0.5){\line(-1,1){1}}
     \put(0,2){\line(1,0){2}}
     \put(0,2){\line(2,-1){1}}

     \end{picture}
$$

\vspace*{1.5cm}

Stating many examples motivates the following conjecture.

\paragraph{Conjecture.} Let $G$ be a $s$-partite well-covered graph with all maximal cliques of size $s$. Then, $G$ is in the class $\cal G$.

At the end of this section, we restate the result of Ravindra about well-covered bipartite graphs.

\begin{corollary}{\rm \cite{24}}  Let $G$ be a bipartite graph with no vertex of degree zero. Then, $G$ is well covered if and only if there is a perfect matching and for each $\{x,y\}$ in this matching, the induced subgraph on $N[\{x,y\}]$ is a complete bipartite graph.
\end{corollary}

{\it Proof.} Let $G$ be well-covered. By Proposition~\ref{partite}, cardinality of both parts are the same and there is a perfect matching in $G$. Moreovere, the edges in the matching make a basic clique cover of $G$. Let $\{x,y\}$ be an edge in the matching. By Theorem~\ref{main}, $G$ is well-covered if and only if any dominating set of $\{x,y\}$ is dependent. The last statement is equal to say that any vertex in $N(\{x\})$ is adjacent to any vertex in $N(\{y\})$,
i.~e., the induced subgraph on $N[\{x,y\}]$ is a complete bipartite graph. \hfill $\Box$

\section{An algebraic interpretation}
There is an interesting algebraic interpretation of well-coveredness of graphs in class $\cal G$, which we state in this section. First we recall some definitions in commutative algebra.

Let $G$ be a graph with vertex set $\{v_1, \ldots, v_n\}$ and $K$ be a field. In the polynomial ring $K[x_1, \ldots, x_n]$, consider $I(G)$ be the ideal generated by all monomials of the form $x_ix_j$ provided that $v_i$ and $v_j$ are adjacent in $G$. This ideal is called edge ideal of the graph $G$ and the quotient ring $R(G)=K[x_1,\ldots,x_n]/ I(G)$ is called edge ring of $G$. This ring is introduced by R. Villarreal \cite{Vil} and has been extensively studied by several mathematicians.

Let $R$ be a commutative ring. An element $a\neq 0$ in $R$ is called zero-divisor if there is a nonzero element $b\in R$ such that $ab=0$. An ideal in $R$ is called monomial ideal if it can be generated by a set of monomials. For example, edge ideal of a graph is a monomial ideal. In a ring of polynomials, it is well known and easy to check that a polynomial $f$ belongs to a monomial ideal if and only if each monomial of $f$ belongs to the ideal. If the monomial ideal is also square-free, then a monomial in $K[x_1,\ldots,x_n]$ belongs to $I$ if and only if its square-free part (its radical) belongs to $I$.
As an example of zero-divisor element, let $R(G)$ be the edge ring of a graph $G$. Let $v_i$ be adjacent to $v_j$ in $G$. The elements $x_i$ and $x_j$ are not zero in $R(G)$ but $x_ix_j=0$. Here, with abuse of notation, we have written $x_i$ as same as its image in $R(G)$.

A term ordering on $K[x_1,\ldots,x_n]$ is a linear order $\preceq$ on the set of terms $\{x_1^{a_1} x_2^{a_2} \ldots x_n^{a_n}\ : \ a_i\in {\Bbb Z}_{\geq 0}, i=1,2,\ldots n \}$, such that for each terms $\alpha, \alpha_1, \alpha_2$,
the following conditions hold.
\begin{itemize}
\item[a)]
if $\alpha_1 \preceq \alpha_2$ then $\alpha_1\alpha\preceq\alpha_2\alpha$.
\item[b)]
$1\preceq\alpha$.
\end{itemize}
Lexicographic, degree lexicographic and degree reverse lexicographic orders are examples of term orderings.  There is a rich literature about term orderings, for instance see \cite{Kr}.

\begin{lemma}\label{linearzero} Let $K$ be a field and $I\subseteq K[x_1,\ldots,x_n]$ be an ideal generated by square-free monomials. Let $f$ be a nonzero linear polynomial in $R=K[x_1,\ldots,x_n]/I$. Then, $f$ is zero-divisor in $R$ if and only if there is a nonzero square-free monomial  $m\in R$ such that $mf=0$.
\end{lemma}

{\it Proof.} Let $f$ be zero-divisor in $R$, then, there is a nonzero polynomial $g$ in $R$ such that $fg=0$.
We may rearrange variables such that $f=x_1+a_2x_2+\cdots+a_sx_s$, $a_j\in K$. Let $\prec$ be the lexicographic order on terms of $K[x_1,\ldots,x_n]$ with respect to $x_1\succ x_2 \succ \cdots \succ x_n$. Let  $g=m_1 + m_2 + \cdots + m_t$ be decomposition of $g$ to nonzero monomials such that $m_1 \succ m_2 \succ\cdots \succ m_t$. Then, in $fg$, the monomial $x_1m_1$ is strictly greater than all other monomials. Therefore, $x_1m_1$ must be zero in $R$. The ideal $I$ is square-free and $x_1m_1\in I$, therefore, we may assume that $x_1\nmid m_1$. By the lexicographic order, we have $x_1\nmid m_i$ for all $1\leq i\leq t$. In other hand, $fg-x_1m_1\in I$. The greatest term of $fg-x_1m_1$ is $x_1m_2$ and then $x_1m_2\in I$ and $fg-(x_1m_1+x_1m_2)\in I$. Continuing this process, we have $x_1m_i\in I$ for all $1\leq i\leq t$ and therefore, $fg-x_1g\in I$. In the polynomial $fg-x_1g$ the greatest term is $x_2m_1$ which must be in $I$. Similarly, $x_2m_i\in I$ for all $1\leq i\leq t$. Finally, we get $x_im_j\in I$ for each $1\leq i\leq s$ and  $1\leq j\leq t$. It means that $m_if\in I$ for each $1\leq i\leq t$. Specially $m_1f\in I$, and because $I$ is square-free and $f$ is linear, we may take  $m_1$ to be square-free. The converse is trivial by definition. \hfill $\Box$\\

Note that in the above lemma, assuming that $I$ is square-free is essential. Because, for example in $K[x_1,x_2]$ assume that $I=\langle x_1^3, x_2^3\rangle$. Then, $(x_1-x_2)(x_1^2+x_1x_2+x_2^2)\in I$, that is $(x_1-x_2)$ is a zero-divisor in  $K[x_1,x_2]/I$ but, there is no any nonzero square-free monomial eliminating $(x_1-x_2)$.

\begin{theorem}\label{zerodiv} Let $G$ be a graph in the class $\cal G$ and $\alpha(G)=k$. Let  $Q_1, \ldots, Q_k$ be a basic clique cover of $G$. Consider
$$
\theta_i=\sum_{v_j \in Q_i} x_j, \ \ \ \ \ i=1,\ldots,k.
$$
Then, $G$ is well-covered if and only if for each $i=1,\ldots,k$, the polynomial $\theta_i$ is not zero-divisor in the ring $R(G)$.
\end{theorem}

{\it Proof.} Let $\theta_i$ be zero-divisor in $R(G)$. By Lemma~\ref{linearzero}, the polynomial $\theta_i$ is zero-divisor in $R(G)$ if and only if there is a nonzero square-free monomial $m$ in $R(G)$ such that $m\theta_i=0$ or equivalently $m\theta_i\in I(G)$.  The ideal $I(G)$ is a monomial ideal, then, for each $v_j$ in $Q_i$, we have $mx_j\in I(G)$. Let $m=x_{i_1}\cdots x_{i_r}$ and $A=\{v_{i_1}, \ldots, v_{i_r}\}$. Then,
$mx_j\in I(G)$ means that there is a vertex $v_{i_l}$ in $A$ such that $v_{i_l}$ is adjacent to $v_j$. This means that the set $A$ is a dominating set of $Q_i$. In other hand, if $v_j$ is in $A\cap Q_i$, then $x_j\theta = x_j^2$ in $R(G)$ and there is $v_{i_l}$ in $A$ adjacent to $v_j$ and therefore $m=0$ in $R(G)$ which is a contradiction. Therefore $A\subseteq V(G)\setminus V(Q_i)$.
Note that $A$ is independent if and only of $m$ is not zero in $R(G)$. Now, Theorem~\ref{main} implies that if $\theta_i$ is a zero-divisor in $R(G)$ for some $1\leq i\leq k$, then, $G$ is not well-covered.

Conversely, if $G$ is not well-covered then, again by Theorem~\ref{main}, there is an independent set $\{v_{i_1}, \ldots, v_{i_r}\}\subseteq V(G)\setminus V(Q_i)$ which dominates $Q_i$ for some $1\leq i\leq k$. In this case, $m=x_{i_1}\cdots x_{i_r}$ is a nonzero monomial in $R(G)$ such that $m\theta_i=0$ and $\theta_i$ is zero-divisor. This completes the proof. \hfill $\Box$\\

Let $G$ be a graph in the class $\cal G$. Then, by Theorem~\ref{zerodiv}, $G$ is well-covered if and only if each polynomial $\theta_i$ is non-zero-divisor in the ring $R(G)$. In other hand, the set of all zero-divisors of $R(G)$ is union of all minimal primes of the ideal $I(G)$. Minimal primes of $I(G)$ are corresponding to minimal vertex covers of $G$. Therefore, checking well-coveredness of the graph $G$ is equal to check that for each $i$, $1\leq i\leq k$, the set of vertices of $Q_i$ is a part of a minimal vertex cover of $G$ or not. But, this is a simple task: it is enough to check that the set of vertices of $Q_i$ is a minimal vertex cover of the induced sub-graph of $G$ on $N(Q_i)$, which can be done in a polynomial time algorithm. Therefore, we have proved the following.

\begin{corollary}
The well-coveredness of a graph in the class $\cal G$ can be checked in polynomial time.
\end{corollary}

We know that an arbitrary graph $G$ is well-covered if and only if the corresponding graph $G(\Delta_G)$ is well-covered.   The graph $G(\Delta_G)$ is in the class $\cal G$ and its well-coveredness can be checked in polynomial time. But, this does not solve completely the problem of well-covered checking of graphs, because passing from $G$ to $G(\Delta_G)$ can not be done in polynomial time. In fact,  the graph $G(\Delta_G)$ has a huge number of vertices in comparison with $G$.

\begin{remark} \rm The next natural question is when a graph in the class $\cal G$ is Cohen-Macaulay. With the notations above, Cohen-Macaulayness of $G$ is equal to regularity of the sequence $\theta_1, \theta_2, \ldots, \theta_k$ in $R(G)$. It means that $\theta_1$ is not zero-divisor in $R(G)$ and for $i=2, \ldots, k$, the element $\theta_i$ is not zero-divisor in $R(G)/\langle \theta_1, \ldots, \theta_{i-1}\rangle$. Therefore, one can say that if $G$ is Cohen-Macaulay, then $G\setminus Q_i$ is Cohen-Macaulay for each $1\leq i\leq k$. It is well-known that a simplicial complex $\Delta$ is Cohen-Macaulay if and only if the graph $G(\Delta)$ is Cohen-Macaulay~(\cite{Stan}). Therefore, to check Cohen-Macaulayness of all simplicial complexes and all graphs, it is enough to check Cohen-Macaulayness of all graphs in the class $\cal G$.
\end{remark}