\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen, filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{epic, eepic, graphics}

\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in \leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Independent Sets on Path-Schemes} \vskip 1cm
\large
Sergey Kitaev \\
Reykjav\'{\i}k University \\
 Ofanleiti 2\\
 IS-103 Reykjav\'{\i}k\\
Iceland \\
\href{mailto:kitaev@ms.uky.edu}{\tt sergey@ru.is}\\
\end{center}


\newtheorem{prop}{Proposition}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{problem}[prop]{Problem}
\theoremstyle{definition}
\newtheorem{defin}[prop]{Definition}
\newtheorem{con}[prop]{Conjecture}
\newtheorem{ex}{Example}
\newtheorem{remark}[prop]{Remark}

\setlength{\unitlength}{4mm}
\newcommand\p{\circle*{0.3}}

\vskip .2 in
\begin{abstract} 
We give the generating function for the
number of independent sets on the class of well-based path-schemes
(a kind of regularly structured graph), which generalizes the known
result in this direction.
\end{abstract}

\bigskip

%\thispagestyle{empty}

%-----------------------------------

\section{Introduction}

Let $G=(V,E)$ be a simple undirected graph with vertex set
$V=\{1,2,\ldots, n\}$ and set of edges $E$. An {\em independent set}
(also called a {\em stable set} in the literature) of $G$ is a subset $S$ of
$V$ such that no two vertices in $S$ are adjacent. The set of all independent
sets of a graph $G$ is denoted by $I(G)$. An independent set is {\em maximal}
if it is not a subset of any larger independent set, and {\em maximum} if
there are no larger independent sets in the graph.
The {\em independence number} $\alpha(G)$ (also called the
{\em stability number}) is the cardinality of a maximum independent set
in $G$.

The two problems of determining maximal and maximum independent sets
have received considerable attention, particularly since the
computation of the independence number is known to be an NP-complete
problem~\cite{karp}. These problems were extensively studied for
various classes of graphs, including trees, forests, (connected)
graphs with at most one cycle, bipartite graphs, $k$-connected
graphs, and others (see~\cite{JouChang} for a survey). The most
efforts are made for the number of maximal independent sets rather
than for finding $\alpha(G)$. However, counting cardinality of
$I(G)$, being a very challenging and interesting enumerative
combinatorics problem, received even less attention, and very few
papers deal with it (see, e.g.,~\cite{BurKitMan, CalkinWilf, EhrKit,
ForbesYcart, Sillke} and references therein). A motivation for
finding $|I(G)|$ is, for instance, the fact that for some classes of
graphs, the set of independent sets $I(G)$ has an interpretation in
terms of other combinatorial objects (see~\cite{BurKitMan, EhrKit}).
For example, Ehrenborg and Kitaev~\cite{EhrKit} showed that there is
a bijection between the set of independent sets of a {\em symmetric
Ferrers graph} on $2n$ vertices and the parts of all compositions
(ordered non-empty partitions) of $n+1$.

The main objective in this paper is to obtain the generating
function for the number of independent sets on the class of {\em
well-based path-schemes} (see Section~\ref{sec1} for definitions),
which generalizes the known result in this
direction~\cite{Sillke}. Although it is possible to provide an
entirely self-contained proof of our main result, we proceed by
reformulating the problem in terms of combinatorics on words, and
then by applying a known result. Providing such a proof we give an
approach to solve some graph theory problems using combinatorics
on words (there are other examples in the literature when a
combinatorics on words approach solves a graph theory problem,
e.g., Evdokimov~\cite{Evdok} constructed chains of maximal length
in the $n$-dimensional unit cube reducing the problem under
consideration to a combinatorics on words problem).

\section{Preliminary}\label{sec1}
Let $V=\{1,2,\ldots, n\}$ and $M$ be a subset of $V$. A {\em
path-scheme} $P(n,M)$ is a graph $G=(V,E)$, where the edge set $E$
is $\{(x,y)\ |\ |x-y| \in M \}$. See Figure~\ref{il} for an example
of a path-scheme.

\begin{figure}[h]
\begin{center}
\begin{picture}(6,2)
\put(0,0){\put(0,0){\p} \put(2,0){\p} \put(4,0){\p} \put(6,0){\p}
\put(8,0){\p} \put(10,0){\p}

\put(0,0.5){1} \put(2,0.5){2} \put(4,0.5){3} \put(5.5,0.5){4}
\put(7.5,0.5){5} \put(9.6,0.5){6}

\spline(0,0)(2,-1)(4,0)
\spline(2,0)(4,-1)(6,0)\spline(4,0)(6,-1)(8,0)\spline(6,0)(8,-1)(10,0)

\spline(0,0)(4,2.5)(8,0)\spline(2,0)(6,2.5)(10,0) }
\end{picture}
\caption{The path-scheme $P(6,\{2,4\})$.} \label{il}
\end{center}
\end{figure}

Note that from the definition, $P(n,M)$ is a simple graph, and thus
its adjacency matrix $A$ is symmetric. Moreover, if the columns and
rows of $A$ are ordered naturally, that is, node $i$ corresponds to
the $i$-th column and to the $i$-th row, then for $1\leq i<j<n$,
$A(i,j)=A(i+1,j+1)$, since $|i-j|$ is in $M$ if and only if
$|(i+1)-(j+1)|$ is in $M$. Thus, we can construct the {\em upper
triangular} part of $A$ by shifting the first row to the right, that
is, we place the first row, and row $i+1$ is obtained by shifting
row $i$ one element to the right. Then we use the symmetry to fill
in the remain entries of $A$.

Suppose $k\geq 2$ and $\mathcal{A}=\{A_1,A_2,\ldots,A_k\}$
is a set of words of the
form $A_i=1\underbrace{0\ldots 0}_{a_i-1}1$, where $a_i\geq 1$, and
$a_i<a_j$ if $i<j$. Moreover, we assume that for any $i>1$ and
$A_i\in\mathcal{A}$, if we replace any number of 0's in $A_i$ by 1's, then
we obtain a word $A'_i$ that contains the word $A_j\in\mathcal{A}$ as a
subword for some
$j<i$. In this case, we call $\mathcal{A}$ {\em well-based set}, and we call
the sequence of $a_i$s associated with $\mathcal{A}$
{\em well-based sequence}.

Any well-based set must contain the word 11. Indeed, if we replace
all 0's by 1's in, say, $A_2$ then $A_1$ must be a subword of the
obtained word. So, we may extend our definition to the case $k=1$.
We define $\mathcal{A}=\{11\}$ to be a well-based set. We see that
any well-based sequence starts from 1, and, clearly, if we take
any number of consecutive initial elements of a well-based
sequence, we get a well-based sequence. A few examples of
well-based sets and associated with them sequences are given in
Table~\ref{tab} ($i$ copies of 0 is denoted by $0^i$).
\begin{table}
\begin{center}
\begin{tabular}{l|l}
Well-based set & Corresponding well-based sequence \\
\hline
$\{ 11, 101, 1001, \ldots, 10^{k-1}1\}$
& $1, 2, 3, \ldots, k$ \\[2mm]
$\{11, 1001, 100001, \ldots, 10^{2m}1 \}$ & $1,3,5,\ldots,2m+1$ \\[2mm]
$\{11,101,1001,1000001, 10000001\}$ & 1,2,3,6,7 \\
\end{tabular}
\smallskip
\caption{Examples of well-based sets and well-based sequences}\label{tab}
\end{center}
\end{table}

We call a scheme $P(n,M)$ a {\em well-based scheme}, if the
elements of $M$ listed in increasing order form a well-based
sequence.

It is known~\cite{Sillke}, that $|I(P(n,\{1\}))|=F(n+2)$ and, more generally,
\begin{equation}\label{known}
|I(P(n,\{1,2,\ldots,k-1\}))|=F_k(n+k),
\end{equation}
where $F(n)$ is the $n$-th Fibonacci
number and $F_k(n)$ is the $n$-th {\em $k$-generalized Fibonacci number}
defined, in our context, as $F_k(1) = \cdots = F_k(k) = 1$ and
$F_k(n) = F_k(n-1) + F_k(n-k)$. Note that in our notation, $F(n)=F_2(n)$.

In Section~\ref{sec2}, we find the generating function for the number of
independent sets of an arbitrary well-based path-scheme. The known
result mentioned above can be extracted from our generating functions, since
it corresponds to a well-based sequence $1,2,\ldots,k-1$.

Before going further, we need some notions and results in a certain area of
combinatorics on words which perhaps can be best described as ``binary
strings and substring avoidance.'' In our presentation we
follow~\cite{Bjorn}, although the original ideas appear
in~\cite{GuibasOdlyzko}.

A {\em binary string} is a string that consists only of the digits
0 and 1. If $X_1=a_0a_1\ldots a_{k-1}$ and $X_2=b_0b_1\ldots
b_{\ell-1}$ are two binary strings of length $k$ and $\ell$
respectively, then the {\em correlation} $c_{12}=c_0c_1\ldots
c_{k-1}$ is the binary string defined with respect to whether
$k\leq \ell$ or $\ell\leq k$ as follows: \begin{itemize}
\item[$k\leq \ell$:] For all $0\leq j\leq k-1$, $c_j=1$ if
$a_i=b_{\ell-k+i+j}$ for all $i=0,1,\ldots,k-j-1$, and $c_j=0$
otherwise; \item[$k>\ell$:] For all $0\leq j\leq k-\ell$, $c_j=1$
if $b_i=a_{k-\ell+i-j}$ for all $i=0,1,\ldots,\ell-1$, and $c_j=0$
otherwise; for all $k-\ell+1\leq j\leq k-1$, $c_j=1$ of
$a_i=b_{\ell-k+i+j}$ for all $i=0,1,\ldots,k-j-1$ and $c_j=0$
otherwise.
\end{itemize} For example, if
$X_1=110$ and $X_2=1011$, then $c_{12}=011$ and $c_{21}=0010$, as
depicted below:
$$\begin{array}{cccccccc}
  &   &   & 1 & 1 & 0 & \ &   \\
\hline
  &   & 1 & 0 & 1 & 1 &   & 0 \\
  & 1 & 0 & 1 & 1 &   &   & 1 \\
1 & 0 & 1 & 1 &   &   &   & 1 \\
\end{array}
\begin{array}{cc}
\ & \ \\
\end{array}
\begin{array}{cccccccc}
  &   & 1 & 0 & 1 & 1 & \ &   \\
\hline
  &   &   & 1 & 1 & 0 &   & 0 \\
  &   & 1 & 1 & 0 &   &   & 0 \\
  & 1 & 1 & 0 &   &   &   & 1 \\
1 & 1 & 0 &   &   &   &   & 0 \\
\end{array}$$
So, in general $c_{ij}\neq c_{ji}$ (they can even be of different lengths).
The {\em autocorrelation} of a word $X_1$ is just $c_{11}$, the
correlation of $X_1$ with itself. For instance, if $X_1=1011$ then
$c_{11}=1001$. This is convenient to interpret a correlation
$c_{ij}=c_0c_1\ldots c_{k-1}$ as a polynomial
$c_{ij}(x)=c_0+c_1x+\cdots +c_{k-1}x^{k-1}$.

The following theorem is the main tool in our considerations.
\begin{theorem}\label{main_tool}{\rm(}\cite[Th. 24]{Bjorn}{\rm)}
The generating function for the number of binary strings that avoid the
substrings $b_1$, $b_2,\ldots, b_n$, of length $\ell_1$,
$\ell_2, \ldots,\ell_n$ respectively, none included in any other, is
given by the formula
\begin{equation}\label{main} S(x)=
\frac{\begin{array}{|ccc|} -c_{11}(x) & \cdots & -c_{1n}(x) \\
\vdots & \ddots & \vdots \\ -c_{n1}(x) & \cdots & -c_{nn}(x)
\end{array}}{\ \ \begin{array}{|cccc|} (1-2x) & 1 & \cdots & 1 \\ x^{\ell_1} & -c_{11}(x) & \cdots & -c_{1n}(x) \\
 \vdots & \vdots & \ddots & \vdots \\ x^{\ell_n} & -c_{n1}(x) & \cdots & -c_{nn}(x) \end{array}\ \ }\ . \end{equation}
\end{theorem}

\section{Main Result}\label{sec2}

Our main result in this paper is the following theorem.

\begin{theorem}\label{mainthm} Let $M=\{a_1,a_2,\ldots, a_k\}$ be a subset of
$V=\{1,2,\ldots,n\}$ such that the sequence $a_1,a_2,\ldots,a_k$
is well-based {\rm(}in particular, $a_1=1${\rm)}. Let
$c(x)=1+\sum_{i=1}^{k}x^{a_i}$. Then the generating function for
the number of independent sets on the well-based path-scheme
$P=P(n,M)$ {\rm(}with vertex set $V${\rm)} is given by
$$G(x)=\frac{c(x)}{(1-x)c(x)-x}.$$
\end{theorem}

\begin{proof} If $x$ is a vertex in $P$, we denote by $N(x)$ the set of its
neighbors in $P$. We identify independent sets with the corresponding
(0,1)-incidence vectors, indexed by $V$. These vectors are called
{\em stable vectors} in some literature. Let $S(P)$ denote the set of
all stable vectors of $P$. Then
$$S_n(P)=\{T\in\{0,1\}^n\ |\ \forall x\in V \ T(x)=1 \Rightarrow T(y)=0 \ \forall y\in N(x)\}.$$
Thus, our goal is equivalent to finding the generating function
for $|S_n(P)|$.

Let $A$ be the adjacency matrix of $P$ with rows and columns ordered
naturally. One can see that the first row of $A$ has 0's everywhere except
for the entries $A(1,a_i+1)$, where $i=1,2,\ldots, k$. Indeed, if
$A(1,x+1)=1$, and $x\neq a_i$ for some $i$, then we must have $x\in M$,
contradiction.

Recall that the upper triangular part of $A$ is constructed by
shifting the first row to the right, which gives that a vector $T$
belongs to $S_n(P)$ if and only if $T$ avoids each substring
$b_i=1\underbrace{0\ldots 0}_{a_i-1}1$ for $i=1,2,\ldots,k$. Let
us prove the last statement.

We first prove necessity. Assume that for a vector $T\in S_n(P)$,
$T(j)=T(j+a_i)=1$ and $T(t)=0$ for
$j<t<j+a_i$ and $1\leq j\leq n-a_i$. From the way we construct $A$,
$(j+a_i)\in N(j)$. We get a contradiction with the definition of $S_n(P)$.

Let us now prove sufficiency.  We need to show that if a vector $T$
does not belong to $S_n(P)$ then it must contain $b_s$ for some $s$,
$1\leq s\leq k$. A vector $T$ does not belong to $S_n(P)$ if there
exist two adjacent nodes, say $j$ and $h$, $j<h$, such that
$T(j)=T(h)=1$. From the construction of $A$, we must have $h=j+a_i$ for
some $i$, $1\leq i\leq k$. If $T(t)=0$ for all $t$ such that
$j<t<h=j+a_i$ then we are done. If some of $T(t)$, for $j<t<h$, are not
0's, $T$ must contain $b_s$ for some $s$, $1\leq s < i$ due to the
fact, that the sequence of $a_i$s is well-based, and therefore the set
$\{b_1,b_2,\ldots,b_k\}$ is well-based (this set is associated with the
sequence)\footnote{Note that this is the only place we use the fact
that the sequence $a_1, a_2,\ldots, a_k$ is well-based.}.

So, $|S_n(P)|$ is given by the number of different binary strings
avoiding the substrings $b_1$, $b_2, \ldots, b_k$, and we may use
Theorem~\ref{main_tool} since none of $b_i$s is included in any
other.

One can easily check that the autocorrelation
$c_{ii}(x)=1+x^{a_i}$, and for $i<j$, the correlations
$c_{ij}(x)=x^{a_i}$ and $c_{ji}(x)=x^{a_j}$. The corresponding
lengths are $\ell_i=a_i+1$, for $1\leq i\leq k$. Thus~(\ref{main})
in our case is
$$G(x)=
\frac{\begin{array}{|cccc|} -(1+x^{a_1}) & -x^{a_1} & \cdots & -x^{a_1} \\ -x^{a_2} & -(1+x^{a_2}) & \cdots & -x^{a_2} \\ \vdots & \vdots & \ddots & \vdots \\ -x^{a_k} & -x^{a_k} & \cdots & -(1+x^{a_k}) \end{array}}{\ \ \begin{array}{|ccccc|} (1-2x) & 1 & 1 & \cdots & 1 \\ x^{a_1+1} & -(1+x^{a_1}) & -x^{a_1} & \cdots & -x^{a_1} \\ x^{a_2+1} & -x^{a_2} & -(1+x^{a_2}) & \cdots & -x^{a_2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\  x^{a_k+1} & -x^{a_k} & -x^{a_k} & \cdots & -(1+x^{a_k}) \end{array}\ \ }\ . $$

To take the determinant in the numerator, we replace the first row
by the sum of all the rows, then factor out some terms from the
determinant, and then add to each column the first one multiplied
by (-1) to get
$$ (-1)^k\cdot(1+\sum_{i=1}^{k}x^{a_i}) \cdot \begin{array}{|ccccc|} 1 & 0 & 0 & \cdots & 0 \\ x^{a_2} & 1 & 0 & \cdots & 0 \\ x^{a_3} & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x^{a_k} & 0 & 0 & \cdots & 1 \end{array}=(-1)^k\cdot c(x).$$

To take the determinant in the denominator, we may replace the first column by
the sum of the first column and the last column times $x$; we replace any
column $i$, $1<i<k+1$ by the sum of column $i$ and the last column times (-1).
Finally, we replace the last row by the sum:
$$\frac{x}{1-x}\cdot\mbox{(row 1) + (row 2) + }\cdots\mbox{ + (row (k+1))},$$
to get an upper triangular matrix having the determinant
$$(-1)^k\cdot (1-x)\left(1-\frac{x}{1-x}+\sum_{i=1}^{k}x^{a_i}\right)= (-1)^k\cdot((1-x)c(x)-x).$$

Thus the statement is proved.
\end{proof}

Let us discuss some corollaries to Theorem~\ref{mainthm}.

If $M=\{1,2,\ldots,k-1\}$ then we can apply our theorem, since the sequence
$1,2,\ldots,k-1$ is well-based. In this case, we get
$$G(x)=\sum_{n\geq 0}g_nx^n=\frac{1+x+\cdots +x^{k-1}}{1-x-x^k},$$
and thus, using the form of the generating function, the sequence
$g_n=|I(P(n,M))|$ satisfies the recurrence $g_n=g_{n-1}+g_{n-k}$ with
$g_{1-k}=g_{2-k}=\cdots =g_{0}=1$, which agrees with~(\ref{known}).

If $M=\{1,3,5\}$ then $M$ is well-based. Theorem~\ref{mainthm}
gives us that $$G(x)=\sum_{n\geq
0}w_nx^n=\frac{1+x+x^3+x^5}{1-x-x^2+x^3-x^4+x^5-x^6}.$$ Thus, in
this case the sequence $w_n$ satisfies the recurrence formula
$$w_n=w_{n-1}+w_{n-2}-w_{n-3}+w_{n-4}-w_{n-5}+w_{n-6},$$
with the initial conditions: $w_{-5}=w_{-4}=w_{-3}=w_{-2}=w_{-1}=w_{0}=1$. The initial values for $w_n=|I(P(n,M))|$ and
$n\geq 1$ are
$$2, 3, 5, 7, 11, 15, 23, 32, 49, 69, 105, 149, \ldots .$$

Finally, we state the following corollary to Theorem~\ref{mainthm} that
can be proved in a standard way by the partial fraction expansion of
the generating function $G(x)$ from Theorem~\ref{mainthm}.

\begin{cor}\label{cor} Let $M$, $V$, $c(x)$, and $P(n,M)$ satisfy the conditions of
Theorem~\ref{mainthm}. Also, $\rho$ is the largest zero
{\rm(}$|\rho|$ is maximal among all the zeros{\rm)} of the function
$$Q(x)=(1-x)c(x)-x=1-x-x^2+(1-x)\sum_{i=2}^{k}x^{a_i}.$$
Then asymptotically,
the growth rate of $|I(P(n,M))|$ is
$$|I(P(n,M))| \lesssim c|\rho|^n$$
for some constant $c$.
\end{cor}

If $k=1$ in Corollary~\ref{cor} then $\rho=\frac{1+\sqrt{5}}{2}$,
and if $k=2$ there then it can be shown\footnote{This observation
was made by the referee.} that $0.6\leq \rho\leq
\frac{1+\sqrt{5}}{2}$.

\section{Problems on the Well-Based Sets}
Although the paper is devoted to counting independent sets, it is
interesting to consider what can be said on the number of well-based sets.
Can we provide a formula and/or asymptotic for it to specify the
portion of the well-based path-schemes among all path-schemes?

The initial values of the sequence corresponding to the number of
well-based sets was kindly provided to the author by Michael Slone:
$$1, 2, 4, 6, 11, 15, 26, 36, 57, 79, 130, 170, 276, 379, 579, 784,
1249, 1654, 2615, 3515.$$ This sequence appears as \seqnum{A103580}
in \cite{Sloane} and has the following interpretation:
it is the number of non-empty subsets $S$ of ${1,2,\ldots,n}$ that have the
property that no element $x$ of $S$ is a nonnegative integer linear
combination of elements of $S-{x}$.
%-----------------------------------

\def\dtcs{{\em Discrete Mathematics and Theoretical Computer Science\,}}
\def\pias{{\em Procedure Indian Academic Science\,}}
\def\eujc{{\em European J. Combin.\,}}
\def\aam{{\em Advances in Applied Mathematics\,}}
\def\dm{{\em Discrete Math.\,}}
\def\ejc{{\em Electron. J. Combin.\,}}
\def\jcta{{\em J. Comb. Theory Ser. A\,}}
\def\slc{{\em S\'eminaire Lotharingien de Combinatoire\,}}
\def\ars{{Ars Combinatorica\,}}

\def\vv{{Volume\,}}

\begin{thebibliography}{10}

\bibitem{BurKitMan}
{\sc A.~Burstein, S.~Kitaev and T.~Mansour},
Independent sets in certain classes of (almost) regular graphs,
preprint.

\bibitem{CalkinWilf}
{\sc N. Calkin and H. Wilf}, The number of independent sets in a
grid graph. {\em SIAM J. Discrete Math.} {\bf 11} (1998), 54--60.

\bibitem{EhrKit}
{\sc R.~Ehrenborg and S.~Kitaev}, Ferrers graphs, their
independent sets and independence complexes, in preparation.

\bibitem{Evdok} A. Evdokimov,
On the maximal chain length of an unit $n$-dimensional cube,
{\em Math. Notes} {\bf 6}, no.\ 3 (1969), 309--319. (in Russian)

\bibitem{ForbesYcart}
{\sc F. Forbes and B. Ycart}, Counting stable sets on Cartesian products of
graphs, \dm {\bf 186} (1998), 105--116.

\bibitem{GuibasOdlyzko}
{\sc L. J. Guibas and A. M. Odlyzko}, String overlaps, pattern
matching, and nontransitive games, \jcta {\bf 30} (1981), 19--42.

\bibitem{JouChang}
{\sc M. J. Jou and G. J. Chang}, Survey on counting maximal independent
sets, {\em Proceedings of the Second Asian Mathematical Conference},
S. Tangmance and E. Schulz eds., World Scientific, Singapore, 1995, 265--275.

%\bibitem{JouChang1}
%{\sc M. J. Jou and G. J. Chang}, The number of maximum independent sets in
%graphs, {\em Taiwanese Journal of Mathematics} {\bf 4}, No. 4 (2000), 685--695.

\bibitem{karp}
{\sc R. M. Karp}, Reducibility among combinatorial problems, in
R. E. Miller, J. W. Thatcher, eds., {\it Complexity of Computer
Computations}, Plenum Press, New York (1972), 85--103.

\bibitem{Sillke}
{\sc T.~Sillke},
Counting independent sets, \\
\href{http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/stablesets}{http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/stable\_sets}

\bibitem{Sloane}
{\sc N. Sloane}, The On-Line Encyclopedia of Integer Sequences.
Published electronically at
\href{http://www.research.att.com/njas/sequences}{http://www.research.att.com/njas/sequences}

\bibitem{Bjorn}
{\sc B. Winterfjord}, Binary strings and substring avoidance, Master's thesis,
CTH and G\"oteborg University (2002).

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
05C69, 05A15; Secondary 68R15, 05A16.

\noindent \emph{Keywords: } Independent sets, path-schemes,
generating functions, string avoidance.
\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence \seqnum{A103580}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in} \noindent Received August 1 2005; revised version
received February 11 2006.  Published in {\it Journal of Integer
Sequences}, April 19 2006.

\bigskip
\hrule
\bigskip

\noindent Return to \htmladdnormallink{Journal of Integer Sequences
home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in

\end{document}