\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P21}{20(2)}{2013}

\usepackage{amsthm,amsmath,amssymb}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\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}

\newcommand{\cp}{\,\square\,}



\title{\bf On the Cartesian product\\ of non well-covered graphs}

\author{Bert L. Hartnell\thanks{Partially supported by NSERC.}\\
\small Department of Mathematics and Computing Science\\[-0.8ex]
\small Saint Mary's University\\[-0.8ex]
\small Halifax, Nova Scotia, Canada\\
\small\tt bert.hartnell@smu.ca
\and
Douglas F. Rall\thanks{Supported by a grant from the Simons Foundation
(\#209654 to Douglas Rall) and the Herman N. Hipp Endowed Chair.}\\
\small Department of Mathematics\\[-0.8ex]
\small Furman University\\[-0.8ex]
\small Greenville, SC, U.S.A.\\
\small\tt doug.rall@furman.edu
}

\date{\dateline{May 1, 2012}{Apr 21, 2013}{Apr 30, 2013}\\
\small Mathematics Subject Classifications: 05C69, 05C76}


\begin{document}

\maketitle

\begin{abstract}
A graph is well-covered if every maximal independent set has the same
cardinality, namely the vertex independence number.  We answer a question
of Topp and Volkmann (1992) and prove that if the Cartesian product
of two graphs is well-covered, then at least one of them must be well-covered.

\bigskip\noindent \textbf{Keywords:} maximal independent set; well-covered; 
Cartesian product
\end{abstract}


\section{Introduction}


 A {\it well-covered graph} $G$ (Plummer~\cite{mdp1970}) is one in which every maximal independent
set of vertices has the same cardinality. That is, every maximal independent set (equivalently,
every independent dominating set) is a maximum independent set.
This class of graphs has been investigated by many researchers from several different
points of view.  Among these are attempts to characterize those well-covered graphs with a
girth  or a maximum degree restriction.  For more details on these approaches as well as
others see the surveys by Plummer~\cite{mdp1993} and by Hartnell~\cite{h1999}.

Topp and Volkmann~\cite{tv1992} investigated how the standard graph
products interact with the class of well-covered graphs.  They asked the following
question that was restated by Fradkin~\cite{f2009}.

\begin{question} {\rm (\cite{tv1992})} \label{ques:1}
Do there exist non well-covered graphs whose Cartesian product is well-covered?
\end{question}

The principal result of this paper is the following theorem that answers Question~\ref{ques:1} in the
negative.

\begin{theorem}\label{thm:main} 
  If $G$ and $H$ are graphs whose Cartesian product is well-covered,
  then at least one of $G$ or $H$ is well-covered.
\end{theorem}

In Section~\ref{sec:defs} we define the terms used most often in this paper; standard
graph theory terminology is used throughout. We then establish Theorem~\ref{thm:main}
in Section~\ref{sec:mainresults}.


\section{Definitions} \label{sec:defs}

If $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are any two graphs, the {\it Cartesian
product} of $G_1$ and $G_2$ is the graph denoted $G_1\cp G_2$ whose vertex
set is the Cartesian product of their vertex sets $V_1 \times V_2$.  Two vertices
$(x_1,x_2)$ and $(y_1,y_2)$ are adjacent in $G_1\cp G_2$ if either
$x_1=y_1$ and $x_2y_2\in E_2$, or $x_1y_1 \in E_1$ and $x_2=y_2$. Note that if
$I_1$ is independent in $G_1$ and $I_2$ is independent in $G_2$, then
the set $I_1\times I_2$ is independent in $G_1\cp G_2$.

For an arbitrary graph $G$ we follow Fradkin~\cite{f2009} and define
a {\it greedy independent decomposition}  of $G$ to be a partition
$A_1,A_2, \ldots, A_t$ of $V(G)$ such that $A_1$ is a maximal independent set in $G$, and
 for each $2 \le i \le t$, the set $A_i$ is a maximal independent set in the
graph $G-(A_1\cup \cdots\cup A_{i-1})$.
One way to construct maximal independent sets in the Cartesian product
$G\cp H$ is to select any greedy independent decomposition $A_1,A_2, \ldots, A_t$
of $G$ and an arbitrary greedy independent decomposition $B_1,B_2, \ldots, B_s$ of
$H$ and combine them into what is called a ``diagonal'' set of the product
as $M=\cup_i(A_i \times B_i)$.  If $s \neq t$, then there are as many sets in this
union as the smaller of $s$ and $t$.

For a vertex $x$ of a graph $G$, the {\em open neighborhood} of $x$ is the set $N(x)$ defined
by $N(x)=\{w\in V(G)\,|\, xw \in E(G)\}$, and the {\em closed neighborhood}, $N[x]$, of $x$ is the set
$N(x) \cup \{x\}$.  For $A\subseteq V(G)$ we define $N(A)$ to be $\cup_{x \in A}N(x)$ and
$N[A]=N(A)\cup A$.
The {\it vertex independence number} of a graph $G$ is the cardinality of a largest
independent set in $G$.  We denote the vertex independence number of $G$ by $\alpha(G)$
and refer to an independent set of this order as an $\alpha(G)$-set.
If a graph $G$ has an independent set $M$ such that $G-N[M]=\{x\}$
for some vertex $x$, then $x$ is said to be an {\em isolatable vertex} of
$G$.  The existence of such a vertex is central to our work.


\begin{lemma} \label{lem:cliqueremainder}
Let $G$ be a graph in which no vertex is isolatable.  If $I$ is any maximum
independent set in $G$ and $x$ is any vertex of $I$, $G-N[I-\{x\}]$ is a clique
of order at least two.
\end{lemma}
\begin{proof}
Suppose $I$ is an $\alpha(G)$-set and that $I$ has a vertex $v$ such that the graph
$G-N[I-\{v\}]$ has an independent set $A$ of size at least two.  Then
$I'=(I -\{v\})\cup A$ is independent in $G$ and has order larger than $|I|=\alpha(G)$,
a contradiction.   Therefore, $G-N[I-\{v\}]$ is a clique.  Since $G$ has no isolatable
vertex it follows that $G-N[I-\{v\}]$ has order at least two. 
\end{proof}


\section{Main Results} \label{sec:mainresults}

We first reduce the study of when a Cartesian product is well-covered
by considering the existence of isolatable vertices in the two factors.

\begin{theorem} \label{thm:firstone}
Suppose that $H$ is not well-covered and $G$ has an isolatable vertex.
Then $G \cp H$ is not well-covered.
\end{theorem}
\begin{proof}
Let $A$ and $B$ be maximal independent subsets of $H$ with $|A|>|B|$,
and suppose that $x$ is an isolatable vertex in $G$.  Let $I$ be an
independent set in $G$ such  that $x$ is an isolated vertex in the graph
$G-N[I]$.  Extend the independent
set $I \times A$ to a maximal independent set $J$ of $(G-N[x])\cp H$.
Let $m=|J|$.  Note that $J$ dominates $N_G(x) \times A$ (and perhaps
other vertices of $N_G(x) \times V(H)$), but $J$ does not contain any
vertices from $N_G[x] \times V(H)$.

Let $J_1=J \cup (\{x\} \times A)$ and $J_2=J \cup (\{x\} \times B)$.
By the choice of $A$ and $B$ it is clear that $|J_1| > |J_2|$.
Let
$X_A$ denote the set of vertices in $N_G(x) \times V(H)$ that are not
dominated by $J_1$.  Similarly, let $X_B$ denote the set of vertices
in $N_G(x) \times V(H)$ that are not dominated by $J_2$.
Note that any vertex in $N_G(x) \times V(H)$ that is dominated by $J_1$
is also dominated by $J$. Since $J \subset J_2$, it follows that if
a vertex of $N_G(x) \times V(H)$
is dominated by $J_1$ it is also dominated by $J_2$.   Hence, the set
$X_B$ is a subset of $X_A$.

Choose a maximal independent set $L$ of the subgraph of $G \cp H$
induced by $X_B$.  Then $J_2 \cup L$ is a maximal independent set
in $G \cp H$.  Extend $L$ to a maximal independent set $M$ of the
subgraph of $G \cp H$ induced by $X_A$.  Now, $J_1 \cup M$ is a
maximal independent set of $G \cp H$, and
\[|J_1 \cup M| = |J_1|+|M|>|J_2|+|M| \ge |J_2|+|L|=|J_2 \cup L|\,.\]
Therefore, $G\cp H$ has maximal independent sets of distinct
cardinalities, and thus $G \cp H$ is not well-covered. 
\end{proof}

It now follows that if both of $G$ and $H$ are not well-covered but $G\cp H$ is
well-covered, then neither $G$ nor $H$ has an isolatable vertex.

\begin{lemma} \label{lem:samesizedisjoint}
Let $G$  and $H$ be graphs such that neither has an isolatable vertex.
If $G\cp H$ is well-covered, then  both
$G$ and $H$ have the property that if $M$ is any maximal independent set
of the graph, that graph must have a maximal independent set $N$ that is
disjoint from $M$.  Furthermore, at least one of $G$ or $H$ has the property
that any two disjoint maximal independent sets have the same cardinality.
\end{lemma}
\begin{proof}
As stated above, neither $G$ nor $H$ has an isolatable vertex.
Let $I_1,I_2, \ldots, I_t$ be  any greedy independent decomposition of $G$ and
$J_1,J_2, \ldots, J_s$ be any greedy independent decomposition of $H$.  Let $p=\min\{s,t\}$.
The (so-called ``diagonal'') set
$M= (I_1\times J_1) \cup (I_2\times J_2) \cup \cdots \cup (I_p\times J_p)$
is maximal independent in $G\cp H$.  Since $G \cp H$ is well-covered, this
implies that $\alpha(G\cp H)=|M|=\sum_{k=1}^p |I_k|\!\cdot\!|J_k|$.

Since $J_1$ is an independent set in $H$ and $J_2$ is a maximal independent
set in $H-J_1$, if there exists a vertex $u\in J_1$ that is not dominated by
$J_2$, then $u$ is isolated in $H-N[J_2]$.  (This follows since every neighbor
of $u$ in $H$ would thus belong to $V(H)-(J_1 \cup J_2)$, and none of these
remains in $H-N[J_2]$.)  This contradicts the fact that
$H$ does not have an isolatable vertex.  Therefore, $J_2$ is actually a maximal
independent set in $H$ as well as in $H-J_1$.  By an identical argument it follows that
$I_2$ is a maximal independent set in $G$.  Suppose that $a=|J_1|$ and $b=|J_2|$
and that $a\neq b$.  Let $c=|I_1|$ and $d=|I_2|$.  Since $I_1$ and $I_2$ are
disjoint maximal independent sets in $G$, the list
$I_2,I_1,I_3,\ldots,I_t$ is also a greedy independent decomposition of $G$.  This implies
\[ca+db+\sum_{k=3}^p|I_k|\!\cdot\!|J_k| =\alpha(G \cp H)=da+cb + \sum_{k=3}^p|I_k|\!\cdot\!|J_k|\,,\]
since $G\cp H$ is well-covered, and thus $ca+db=da+cb$.  Since $a\neq b$ we get $c=d$; that is, $|I_1|=|I_2|$.
Since $I_1,I_2, \ldots, I_t$ is an arbitrary greedy independent decomposition of
$G$, the lemma follows. 
\end{proof}


We now proceed to prove our main result.
\setcounter{theorem}{1}
\begin{theorem}
  If $G$ and $H$ are graphs such that $G\cp H$ is well-covered, then
  at least one of $G$ or $H$ is well-covered.
\end{theorem}
\begin{proof}
Suppose by way of contradiction that the statement is not true.  Let $G$
and $H$ be a pair of graphs neither of which is well-covered but such that
$G \cp H$ is well-covered.  As above we may assume that no vertex of
either $G$ or $H$ can be isolated in its own graph.  From Lemma~\ref{lem:samesizedisjoint}
we may assume without loss of generality that $G$ has the property that any
two maximal independent sets of different cardinalities must intersect nontrivially.

Since $G$ is not well-covered, there exists a maximal independent set whose cardinality
is less than $\alpha(G)$.  From the collection of all maximal independent sets in $G$
choose a pair, say $I$ and $J$,  such that $|J|<|I|=\alpha(G)$ and
$|I \cap J|$ is as small as possible.
Since $|I| \neq |J|$ there exists $v \in I\cap J$.  Let $F=G-N[I-\{v\}]$.
By Lemma~\ref{lem:cliqueremainder} this subgraph $F$ is a clique of order at least two.
Let $w$ be any vertex of $F$ such that $w \neq v$, and let $I'=(I-\{v\})\cup \{w\}$.
Note that $I'$ is independent, $|I'|=|I|$,  and yet
$|I'\cap J|=|I \cap J|-1$ contradicting our choice of $I$ and $J$.
Therefore, $G$ is well-covered.
\end{proof}



\begin{thebibliography}{9}


\bibitem{f2009}
A.~O.~Fradkin. \newblock On the well-coveredness of Cartesian products
 of graphs. \newblock {\em Discrete Math.}, 309:238--246, 2009.

\bibitem{h1999}
B.L.~Hartnell. \newblock Well-covered graphs. \newblock {\em  J. Combin. Math. Combin. Comput.},
29:107--115, 1999.

\bibitem{mdp1970}
M.D.~Plummer. \newblock Some covering concepts in graphs. \newblock {\em J. Combin. Theory},
8:91--98, 1970.

\bibitem{mdp1993}
M.~D.~Plummer. \newblock Well-covered graphs: a survey. \newblock {\em Quaestiones Math.},
16(3):253--287, 1993.

\bibitem{tv1992}
J.~Topp and L.~Volkmann. \newblock On the well coveredness of products of graphs. 
\newblock {\em Ars Combin.}, 33:199--215, 1992.


\end{thebibliography}


\end{document}


























