\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 i1$ 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*\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*