# Independence complex of the lexicographic product of a forest

Kengo Okura  Osaka Prefecture University, 1-1 Gakuen-cho, Naka-ku, Sakai,
Osaka 599-8531, Japan<EMAIL_ADDRESS>
###### Abstract.

We study the independence complex of the lexicographic product ${G}[{H}]$ of a
forest $G$ and a graph $H$. We prove that for a forest $G$ which is not
dominated by a single vertex, if the independence complex of $H$ is homotopy
equivalent to a wedge sum of spheres, then so is the independence complex of
${G}[{H}]$. We offer two examples of explicit calculations. As the first
example, we determine the homotopy type of the independence complex of
${L_{m}}[{H}]$, where $L_{m}$ is the tree on $m$ vertices with no branches,
for any positive integer $m$ when the independence complex of $H$ is homotopy
equivalent to a wedge sum of $n$ copies of $d$-dimensional sphere. As the
second one, for a forest $G$ and a complete graph $K$, we describe the
homological connectivity of the independence complex of ${G}[{K}]$ by the
independent domination number of $G$.

###### Key words and phrases:

independence complex, lexicographic product, homotopy type, grid graph

###### 2020 Mathematics Subject Classification:

05C69, 05C76, 55P15

##  1\. Introduction

In this paper, a graph $G$ always means a finite undirected graph with no
multiple edges and loops. Its vertex set and edge set are denoted by $V(G)$
and $E(G)$, respectively. A subset $\sigma$ of $V(G)$ is an independent set if
any two vertices of $\sigma$ are not adjacent. The independent sets of $G$ are
closed under taking subset, so they form an abstract simplicial complex. We
call this abstract simplicial complex the independence complex of $G$ and
denote by $I(G)$. In the rest of this paper, $I(G)$ denotes a geometric
realization of $I(G)$ unless otherwise noted.

Independence complexes of graphs are no less important than other simplicial
complexes constructed from graphs and have been studied in many contexts. In
particular, the independence complexes of square grid graphs are studied by
Thapper [15], Iriye [11] and many other researchers. It is conjectured by
Iriye [11, Conjecture 1.8] that the independence complex of cylindrical square
grid graph is always homotopy equivalent to a wedge sum of spheres. Discrete
Morse theory , introduced by Forman [8] and reformulated by Chari [5], is one
of the effective methods for determining the homotopy type of independence
complex. Bousquet-Mélou, Linusson and Nevo [4] and Thapper [15] studied the
independence complexes of grid graphs by performing discrete Morse theory as a
combinatorial algorithm called matching tree. However, it is hard to
distinguish two complexes which has the same number of cells in each dimension
only by discrete Morse theory. This is precisely the situation which we have
to deal with in this paper. We need topological approaches in case that
discrete Morse theory is not available. For example, it is effective to
represent an independence complex of a graph as a union of independence
complexes of subgraphs, as in Engström [7], Adamaszek [1] and Barmak [3].

Let $L_{m}$ be a tree on $m$ vertices with no branches, and $C_{n}$ be a cycle
on $n$ vertices ($n\geq 3$). Namely

$\displaystyle V(L_{m})=\\{1,2,\ldots,m\\},$ $\displaystyle E(L_{m})=\\{ij\ |\
|i-j|=1\\},$ $\displaystyle V(C_{n})=\\{1,2,\ldots,n\\},$ $\displaystyle
E(C_{n})=E(L_{n})\cup\\{n1\\}.$

Related to the above previous researches, we focus on the fact that the
cylindrical square grid graphs are obtained from $L_{m}$ and $C_{n}$ by a
certain “product” construction. As Harary [10] mentioned, there are various
ways to construct a graph structure on $V(G_{1})\times V(G_{2})$ for given two
graphs $G_{1}$ and $G_{2}$. A cylindrical square grid graph is the Cartesian
product of $L_{m}$ and $C_{n}$ for some $m,n$. In this paper, we are
interested in the lexicographic product of two graphs, which is defined as
follows.

######  Definition 1.1.

Let $G,H$ be graphs. The lexicographic product ${G}[{H}]$ is a graph defined
by

$\displaystyle V({G}[{H}])=V(G)\times V(H),$ $\displaystyle
E({G}[{H}])=\left\\{(u_{1},v_{1})(u_{2},v_{2})\ \middle|\ \begin{aligned}
&u_{1}u_{2}\in E(G)\\\ &\text{ or}\\\ &u_{1}=u_{2},v_{1}v_{2}\in
E(H)\end{aligned}\right\\}.$

${L_{4}}[{L_{3}}]$ |  | ${L_{3}}[{L_{4}}]$
---|---|---
Figure 1. Lexicographic products ${L_{4}}[{L_{3}}]$ and ${L_{3}}[{L_{4}}]$.

Harary [10] called this construction the composition. A lexicographic product
${G}[{H}]$ can be regarded to have $|V(G)|$ pseudo-vertices. Each of them is
isomorphic to $H$ and two pseudo-vertices are “adjacent” if the corresponding
vertices of $G$ are adjacent. Graph invariants of lexicographic product have
been investigated by, for example, Geller and Stahl [9]. Independence
complexes of lexicographic products are studied by Vander Meulen and Van Tuyl
[16] from combinatorial point of view.

We try to reveal in what condition the independence complex of a lexicographic
product is homotopy equivalent to a wedge sum of spheres. The main result of
this paper is the following theorem.

######  Theorem 1.2.

Let $G$ be a forest and $H$ be a graph. We call $G$ a star if there exists
$v\in V(G)$ such that $uv\in E(G)$ for any $u\in V(G)\setminus\\{v\\}$.
Suppose that $I(H)$ is homotopy equivalent to a wedge sum of spheres. Then, we
have the followings.

  1. (1)

If $G$ is a star on at least $2$ vertices, then $I({G}[{H}])$ is homotopy
equivalent to a disjoint union of two wedge sums of spheres.

  2. (2)

If $G$ is not a star, then $I({G}[{H}])$ is homotopy equivalent to a wedge sum
of spheres.

For example, Kozlov [13, Proposition 5.2] proved that $I(C_{n})$ is homotopy
equivalent to a wedge sum of spheres. So, it follows from Theorem 1.2 that
$I({L_{m}}[{C_{n}}])$ with $m\geq 4$ is homotopy equivalent to a wedge sum of
spheres. Remark that ${L_{m}}[{C_{n}}]$ contains a cylindrical square grid
graph as a subgraph which is obtained from ${L_{m}}[{C_{n}}]$ by removing
edges. Furthermore, we determined the homotopy type of $I({L_{m}}[{H}])$ for
any $m\geq 1$ and a graph $H$ such that $I(H)$ is homotopy equivalent to $n$
copies of $k$-dimensional spheres. We denote the $d$-dimensional sphere by
$S^{d}$ and a wedge sum of $n$ copies of CW complex $X$ by $\bigvee_{n}X$.

######  Theorem 1.3.

Let $H$ be a graph such that $I(H)\simeq{\bigvee}_{n}S^{k}$ with $n\geq 1$,
$k\geq 0$. Then we have

$\displaystyle I({L_{m}}[{H}])$ $\displaystyle\simeq$
$\displaystyle\left\\{\begin{aligned} &{\bigvee}_{n}S^{k}&&(m=1),\\\
&\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}S^{k}\right)&&(m=2),\\\
&\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n^{2}}S^{2k+1}\right)&&(m=3),\\\
&\bigvee_{0\leq
p\leq\frac{m+1}{2}}\left(\bigvee_{pk-1+\max\left\\{p,\frac{m}{3}\right\\}\leq
d\leq
pk+\frac{m+p-2}{3}}\left({\bigvee}_{N_{m,n,k}(p,d)}S^{d}\right)\right)&&(m\geq
4),\end{aligned}\right.$

where

$\displaystyle N_{m,n,k}(p,d)$
$\displaystyle=n^{p}\binom{d-pk+1}{p}\binom{p+1}{3(d-pk+1)-m}.$

Here, $\binom{l}{r}$ denotes the binomial coefficient. We define
$\binom{l}{r}=0$ if $r<0$ or $l<r$.

The rest of this paper is organized as follows. In Section 2, we define
notations on graphs and state some of the basic properties of independence
complexes of graphs. Section 3 is the main part of this paper. It first
provides a condition for the independence complex of a graph to be the union
of the independence complexes of given two full subgraphs (Lemma 3.2). Note
that the cofiber sequence studied by Adamaszek [1, Proposition 3.1] is a
special case of this decomposition. Using this result, we obtain a
decomposition of an independence complex of a lexicographic product, which is
essentially important to achieve our purpose (Theorem 3.1). Then, we prove
Theorem 1.2. Here we need an observation on the unreduced suspension of a
disjoint union of two spaces (Lemma 3.5). Section 4 contains two examples of
the explicit calculations. The first one is the proof of Theorem 1.3. The
second one is on the relationship between the homological connectivity of
$I({G}[{H}])$ and the independent domination number of a forest $G$ (Theorem
4.3).

##  2\. Preliminaries

In this paper, a graph always means a finite undirected simple graph $G$. It
is a pair $(V(G),E(G))$, where $V(G)$ is a finite set and $E(G)$ is a subset
of $2^{V(G)}$ such that $|e|=2$ for any $e\in E(G)$. An element of $V(G)$ is
called a vertex of $G$, and an element of $E(G)$ is called an edge of $G$. In
order to indicate that $e=\\{u,v\\}$ ($u,v\in V(G)$), we write $e=uv$.

For a vertex $v\in V(G)$, an open neighborhood $N_{G}(v)$ of $v$ in $G$ is
defined by

$\displaystyle N_{G}(v)=\\{u\in V(G)\ |\ uv\in E(G)\\}.$

A closed neighborhood $\overline{N}_{G}(v)$ of $v$ in $G$ is defined by
$\overline{N}_{G}(v)=N_{G}(v)\sqcup\\{v\\}$.

A full subgraph $H$ of a graph $G$ is a graph such that

$\displaystyle V(H)$ $\displaystyle\subset V(G),$ $\displaystyle E(H)$
$\displaystyle=\\{uv\in E(G)\ |\ u,v\in V(H)\\}.$

For two full subgraphs $H,K$ of $G$, a full subgraph whose vertex set is
$V(H)\cap V(K)$ is denoted by $H\cap K$, and a full subgraph whose vertex set
is $V(H)\setminus V(K)$ is denoted by $H\setminus K$. For a subset $U\subset
V(G)$, $G\setminus U$ is the full subgraph of $G$ such that $V(G\setminus
U)=V(G)\setminus U$.

An abstract simplicial complex $K$ is a collection of finite subsets of a
given set $V(K)$ such that if $\sigma\in K$ and $\tau\subset\sigma$, then
$\tau\in K$. An element of $K$ is called a simplex of $K$. For a simplex
$\sigma$ of $K$, we set $\dim\sigma=|\sigma|-1$, where $|\sigma|$ is the
cardinality of $\sigma$. As noted in Section 1, we do not distinguish an
abstract simplicial complex $K$ from its geometric realization $|K|$.

The independence complex $I(G)$ of a graph $G$ is an abstract simplicial
complex defined by

$\displaystyle I(G)=\\{\sigma\subset V(G)\ |\ uv\notin E(G)\text{ for any
$u,v\in\sigma$ }\\}.$

For a full subgraph $H$ of $G$, $I(H)$ is a subcomplex of $I(G)$. Furthermore,
if $H,K$ are full subgraphs of $G$, then $I(H\cap K)=I(H)\cap I(K)$. The
following proposition is the fundamental property of independence complexes.

######  Proposition 2.1.

Let $G$ be a graph and $G_{1}$ and $G_{2}$ be full subgraphs of $G$ such that
$V(G)=V(G_{1})\sqcup V(G_{2})$.

  1. (1)

If $uv\notin E(G)$ for any $u\in V(G_{1})$ and $v\in V(G_{2})$, then we have

$\displaystyle I(G)=I(G_{1})*I(G_{2}).$

  2. (2)

If $uv\in E(G)$ for any $u\in V(G_{1})$ and $v\in V(G_{2})$, then we have

$\displaystyle I(G)=I(G_{1})\sqcup I(G_{2}).$

###### Proof.

In the proof, we consider $I(G)$ as an abstract simplicial complex.

Suppose that $uv\notin E(G)$ for any $u\in V(G_{1})$ and $v\in V(G_{2})$.
Then, we have

$\displaystyle I(G)$ $\displaystyle=\left\\{\sigma\subset V(G_{1})\sqcup
V(G_{2})\ \middle|\ \left.\begin{aligned} &\sigma\cap V(G_{1})\in I(G_{1})\\\
&\text{ and }\\\ &\sigma\cap V(G_{2})\in
I(G_{2})\end{aligned}\right.\right\\}$ $\displaystyle=I(G_{1})*I(G_{2}).$

Suppose that $uv\in E(G)$ for any $u\in V(G_{1})$ and $v\in V(G_{2})$. Then,
we have

$\displaystyle I(G)$ $\displaystyle=\left\\{\sigma\subset V(G_{1})\sqcup
V(G_{2})\ \middle|\ \left.\begin{aligned} &\sigma\subset V(G_{1})\text{ and
}\sigma\in I(G_{1})\\\ &\text{ or }\\\ &\sigma\subset V(G_{2})\text{ and
}\sigma\in I(G_{2})\end{aligned}\right.\right\\}$
$\displaystyle=I(G_{1})\sqcup I(G_{2}).$

∎

Let $X$ be a CW complex. We denote the unreduced suspension of $X$ by $\Sigma
X$. For subcomplexes $X_{1},X_{2}$ of $X$ such that $X_{1}\cap X_{2}=A$, we
denote the union of $X_{1}$ and $X_{2}$ by $X_{1}\cup_{A}X_{2}$ in order to
indicate that the intersection of $X_{1}$ and $X_{2}$ is $A$.

##  3\. Proof of Theorem 1.2

We first prove the following theorem, which we need to prove Theorem 1.2.

######  Theorem 3.1.

Let $G$ a graph and $v$ be a vertex of $G$. Suppose that there exists a vertex
$w$ of $G$ such that $N_{G}(w)=\\{v\\}$. Let $H$ be a non-empty graph.

  * •

If $G\setminus\overline{N}_{G}(v)=\emptyset$, then we have

$\displaystyle I({G}[{H}])=I(H)\sqcup I({(G\setminus\\{v\\})}[{H}]).$

  * •

If $G\setminus\overline{N}_{G}(v)\neq\emptyset$, then we have

$\displaystyle I({G}[{H}])\simeq$ $\displaystyle\Sigma
I({(G\setminus\overline{N}_{G}(v))}[{H}])\vee\left(I({(G\setminus\overline{N}_{G}(v))}[{H}])*I(H)\right)$
$\displaystyle\ \vee\left(I({(G\setminus\\{v,w\\})}[{H}])*I(H)\right).$

The proof of Theorem 3.1 has two steps. The first step is to decompose
$I({G}[{H}])$ as a union of $I({(G\setminus N_{G}(v))}[{H}])$ and
$I({(G\setminus\\{v\\})}[{H}])$. The second step is to transform this union
into a wedge sum. We need two lemmas corresponding to these two steps.

######  Lemma 3.2.

Let $G$ be a graph and $H,K\subset G$ be full subgraphs of $G$ such that
$V(H)\cup V(K)=V(G)$. Suppose that $v_{1}v_{2}\in E(G)$ for any vertices
$v_{1}\in V(H)\setminus V(K)$ and $v_{2}\in V(K)\setminus V(H)$. Then,

$\displaystyle I(G)=I(H)\cup_{I(H\cap K)}I(K).$

###### Proof.

For a simplex $\sigma$ of $I(G)$, suppose that there exists a vertex
$u_{0}\in\sigma\cap(V(H)\setminus V(K))$. Then, by the assumption of the
lemma, any vertex $v\in V(K)\setminus V(H)$ is adjacent to $u_{0}$. So,
$\sigma\cap(V(K)\setminus V(H))$ must be empty, which means that $\sigma$ is a
simplex of $H$. On the other hand, if $\sigma\cap(V(H)\setminus
V(K))=\emptyset$, then $\sigma$ is a simplex of $K$ since $V(H)\cup
V(K)=V(G)$. ∎

$K$$H$
---
$G$
Figure 2. A graph $G$ and its subgraphs $H,K$ such that $I(G)=I(H)\cup I(K)$.

######  Example 3.3.

For a graph $G$ and a vertex $v\in V(G)$, consider two subgraphs
$G\setminus\\{v\\}$ and $G\setminus N_{G}(v)$ of $G$. We have

$\displaystyle(V(G)\setminus\\{v\\})\setminus(V(G)\setminus
N_{G}(v))=N_{G}(v),$ $\displaystyle(V(G)\setminus
N_{G}(v))\setminus(V(G)\setminus\\{v\\})=\\{v\\},$
$\displaystyle(G\setminus\\{v\\})\cap(G\setminus
N_{G}(v))=G\setminus\overline{N}_{G}(v).$

Then, by Lemma 3.2, we have

$\displaystyle
I(G)=I(G\setminus\\{v\\})\cup_{I(G\setminus\overline{N}_{G}(v))}I(G\setminus
N_{G}(v)).$

Since $I(G\setminus N_{G}(v))=I(G\setminus\overline{N}_{G}(v))*\\{v\\}$, we
obtain a cofiber sequence

which was studied by Adamaszek [1, Proposition 3.1].

######  Lemma 3.4.

Let $X$ be a CW complex and $X_{1},X_{2}$ be subcomplexes of $X$ such that
$X=X_{1}\cup X_{2}$. If the inclusion maps $i_{1}:X_{1}\cap X_{2}\to X_{1}$
and $i_{2}:X_{1}\cap X_{2}\to X_{2}$ are null-homotopic, then we have

$\displaystyle X\simeq X_{1}\vee X_{2}\vee\Sigma(X_{1}\cap X_{2}).$

###### Proof.

Consider the mapping cylinder $M(i_{1},i_{2})$ of $i_{1},i_{2}$. Let $u\in
X_{1}$ and $v\in X_{2}$ be points such that $i_{1}\simeq c_{u}$ and
$i_{2}\simeq c_{v}$, where $c_{u}:X_{1}\cap X_{2}\to X_{1}$ and
$c_{v}:X_{1}\cap X_{2}\to X_{2}$ are the constant map to $u$ and $v$,
respectively. Then, we have

$\displaystyle X=X_{1}\cup X_{2}\simeq M(i_{1},i_{2})\simeq
M(c_{u},c_{v})=X_{1}\vee_{u}\Sigma(X_{1}\cap X_{2})\vee_{v}X_{2}.$

This is the desired conclusion. ∎

###### Proof of Theorem 3.1.

Consider two full subgraphs $K_{1},K_{2}$ of ${G}[{H}]$ defined by

$\displaystyle K_{1}={(G\setminus N_{G}(v))}[{H}],$ $\displaystyle
K_{2}={(G\setminus\\{v\\})}[{H}].$

Then we have

$\displaystyle V(K_{1})\setminus V(K_{2})=\\{v\\}\times V(H),$ $\displaystyle
V(K_{2})\setminus V(K_{1})=N_{G}(v)\times V(H),$ $\displaystyle K_{1}\cap
K_{2}={(G\setminus\overline{N}_{G}(v))}[{H}].$

It follows that $v_{1}v_{2}\in E({G}[{H}])$ for any vertices $v_{1}\in
V(K_{1})\setminus V(K_{2})$ and $v_{2}\in V(K_{2})\setminus V(K_{1})$ since
$uv\in E(G)$ for any $u\in N_{G}(v)$. So, by Lemma 3.2, we obtain

$\displaystyle I({G}[{H}])=I({(G\setminus
N_{G}(v))}[{H}])\cup_{I({(G\setminus\overline{N}_{G}(v))}[{H}])}I({(G\setminus\\{v\\})}[{H}]).$

If $G\setminus\overline{N}_{G}(v)=\emptyset$, then

$\displaystyle I({(G\setminus\overline{N}_{G}(v))}[{H}])$
$\displaystyle=I({\emptyset}[{H}])=I(\emptyset)=\emptyset,$ $\displaystyle
I({(G\setminus N_{G}(v))}[{H}])$ $\displaystyle=I({\\{v\\}}[{H}])=I(H).$

So, the desired formula is obtained directly.

Suppose that $G\setminus\overline{N}_{G}(v)\neq\emptyset$. Let
$i:I({(G\setminus\overline{N}_{G}(v))}[{H}])\to I({(G\setminus
N_{G}(v))}[{H}])$ and $j:I({(G\setminus\overline{N}_{G}(v))}[{H}])\to
I({(G\setminus\\{v\\})}[{H}])$ be the inclusion maps. By Proposition 2.1, we
have

$\displaystyle I({(G\setminus N_{G}(v))}[{H}])$
$\displaystyle=I({((G\setminus\overline{N}_{G}(v))\sqcup\\{v\\})}[{H}])$
$\displaystyle=I({(G\setminus\overline{N}_{G}(v))}[{H}])*I(H),$ $\displaystyle
I({(G\setminus\\{v\\})}[{H}])$
$\displaystyle=I({((G\setminus\\{v,w\\})\sqcup\\{w\\})}[{H}])$
$\displaystyle=I({(G\setminus\\{v,w\\})}[{H}])*I(H).$

The third equality follows from $N_{G}(w)=\\{v\\}$. Here, $I(H)$ is non-empty
since $H$ is non-empty. Let $x\in I(H)$ be a point. Then, we have

$\displaystyle I({(G\setminus\overline{N}_{G}(v))}[{H}])*\\{x\\}$
$\displaystyle\subset I({(G\setminus\overline{N}_{G}(v))}[{H}])*I(H),$
$\displaystyle I({(G\setminus\overline{N}_{G}(v))}[{H}])*\\{x\\}$
$\displaystyle\subset I({(G\setminus\\{v,w\\})}[{H}])*I(H).$

The second inclusion follows from $\\{v,w\\}\subset\overline{N}_{G}(v)$. These
inclusions indicate that $i,j$ are null-homotopic. Therefore, by Lemma 3.4, we
obtain

$\displaystyle I({G}[{H}])=$ $\displaystyle I({(G\setminus
N_{G}(v))}[{H}])\cup_{I({(G\setminus\overline{N}_{G}(v))}[{H}])}I({(G\setminus\\{v\\})}[{H}])$
$\displaystyle\simeq$ $\displaystyle\Sigma
I({(G\setminus\overline{N}_{G}(v))}[{H}])\vee\left(I({(G\setminus\overline{N}_{G}(v))}[{H}])*I(H)\right)$
$\displaystyle\ \vee\left(I({(G\setminus\\{v,w\\})}[{H}])*I(H)\right).$

So, the proof is completed. ∎

In order to derive Theorem 1.2 from Theorem 3.1, we need some topological
observations, which we state in the following two lemmas.

######  Lemma 3.5.

Let $X,Y$ be CW complexes. Then we have

$\displaystyle\Sigma(X\sqcup Y)\simeq\Sigma X\vee\Sigma Y\vee S^{1}.$

###### Proof.

Let $u,v$ be cone points of $\Sigma(X\sqcup Y)$. Then we have

$\displaystyle\Sigma(X\sqcup Y)=\Sigma X\cup_{\\{u,v\\}}\Sigma Y.$

For $x\in X$ and $y\in Y$, there are line segments $xu,xv\subset\Sigma X$ and
$yu,yv\subset\Sigma Y$. So, the inclusion maps $\\{u,v\\}\to\Sigma X$,
$\\{u,v\\}\to\Sigma Y$ are null-homotopic. Therefore, it follows from Lemma
3.4 that

$\displaystyle\Sigma(X\sqcup Y)$ $\displaystyle\simeq\Sigma X\vee\Sigma
Y\vee\Sigma\\{u,v\\}$ $\displaystyle\simeq\Sigma X\vee\Sigma Y\vee S^{1}.$

∎

######  Lemma 3.6.

Let $A$, $B$, $C$ be CW complexes such that each of them is homotopy
equivalent to a wedge sum of spheres. Then, both $A*B$ and $(A\sqcup B)*C$ are
again homotopy equivalent to a wedge sum of spheres.

###### Proof.

We first claim that for any CW complex $X,Y,Z$, we have

$\displaystyle(X\vee Y)*Z\simeq(X*Z)\vee(Y*Z).$

This is because $X*Y$ is homotopy equivalent to $\Sigma(X\land Y)$ for any
pointed CW complexes $(X,x_{0})$ and $(Y,y_{0})$. This homotopy equivalence
yields

$\displaystyle(X\vee Y)*Z$ $\displaystyle\simeq\Sigma((X\vee Y)\land
Z)\simeq\Sigma((X\land Z)\vee(Y\land Z))$ $\displaystyle\simeq\Sigma(X\land
Z)\vee\Sigma(Y\land Z)\simeq(X*Z)\vee(Y*Z)$

as desired.

Let $A=\bigvee_{i}S^{a_{i}}$, $B=\bigvee_{j}S^{b_{j}}$,
$C=\bigvee_{k}S^{c_{k}}$ be arbitrary wedge sums of spheres. It follows from
Lemma 3.5 and above claim that

$\displaystyle A*B$
$\displaystyle\simeq\left(\bigvee_{i}S^{a_{i}}\right)*\left(\bigvee_{j}S^{b_{j}}\right)\simeq\bigvee_{i}\left(S^{a_{i}}*\left(\bigvee_{j}S^{b_{j}}\right)\right)$
$\displaystyle\simeq\bigvee_{i,j}\left(S^{a_{i}}*S^{b_{j}}\right)\simeq\bigvee_{i,j}S^{a_{i}+b_{j}+1},$
$\displaystyle(A\sqcup B)*C$
$\displaystyle\simeq\left(\left(\bigvee_{i}S^{a_{i}}\right)\sqcup\left(\bigvee_{j}S^{b_{j}}\right)\right)*\left(\bigvee_{k}S^{c_{k}}\right)$
$\displaystyle\simeq\bigvee_{k}\left(\left(\left(\bigvee_{i}S^{a_{i}}\right)\sqcup\left(\bigvee_{j}S^{b_{j}}\right)\right)*S^{c_{k}}\right)$
$\displaystyle\simeq\bigvee_{k}\left(\left(\left(\bigvee_{i}S^{a_{i}}\right)*S^{c_{k}}\right)\vee\left(\left(\bigvee_{j}S^{b_{j}}\right)*S^{c_{k}}\right)\vee
S^{c_{k}+1}\right)$
$\displaystyle\simeq\bigvee_{k}\left(\left(\bigvee_{i}S^{a_{i}+c_{k}+1}\right)\vee\left(\bigvee_{j}S^{b_{j}+c_{k}+1}\right)\vee
S^{c_{k}+1}\right)$
$\displaystyle\simeq\left(\bigvee_{i,k}S^{a_{i}+c_{k}+1}\right)\vee\left(\bigvee_{j,k}S^{b_{j}+c_{k}+1}\right)\vee\left(\bigvee_{k}S^{c_{k}+1}\right).$

Therefore, we obtain the desired conclusion. ∎

We are now ready to prove Theorem 1.2.

###### Proof of Theorem 1.2.

We prove the theorem by induction on $|V(G)|$. Before we start, we confirm two
cases.

First, suppose that $G$ is a star on at least $2$ vertices, namely $|V(G)|\geq
2$ and there exists $v\in V(G)$ such that
$G\setminus\overline{N}_{G}(v)=\emptyset$. We have $u_{1}u_{2}\notin E(G)$ for
any $u_{1},u_{2}\in N_{G}(v)=G\setminus\\{v\\}$ since $G$ is a forest. So, by
Theorem 3.1, we get

$\displaystyle I({G}[{H}])$ $\displaystyle=I(H)\sqcup
I({(G\setminus\\{v\\})}[{H}])$
$\displaystyle=I(H)\sqcup\left(\mathop{*}_{|V(G)|-1}I(H)\right).$

Since $|V(G)|-1\geq 1$, the join of copies of $I(H)$ is homotopy equivalent to
a wedge sum of spheres by Lemma 3.6. Therefore, $I({G}[{H}])$ is homotopy
equivalent to a disjoint union of two wedge sums of spheres.

Next, suppose that $G$ has no edges. Then $I({G}[{H}])$ is the join of
$|V(G)|$ copies of $I(H)$, which is a wedge sum of spheres by Lemma 3.6.

Now we start the induction. The forest $G$ with $|V(G)|\leq 2$ is isomorphic
to one of $L_{1}$, $L_{2}$ and $L_{1}\sqcup L_{1}$. They are included in the
above cases. Hence, for a forest $G$ with $|V(G)|\leq 2$, $I({G}[{H}])$ is
homotopy equivalent to a wedge sum of spheres or a disjoint union of two wedge
sums of spheres.

Assume that for any forest $G^{\prime}$ such that $|V(G^{\prime})|\leq n$,
$I({G^{\prime}}[{H}])$ is homotopy equivalent to a wedge sum of spheres or a
disjoint union of two wedge sums of spheres. Let $G$ be a forest with at least
one edge such that $|V(G)|=n+1$ and
$G\setminus\overline{N}_{G}(v)\neq\emptyset$ for any $v\in V(G)$. Then, since
$G$ is a forest, there exists $w\in V(G)$ such that $N_{G}(w)=\\{v\\}$ for
some $v\in V(G)$ (namely a leaf $w$ of $G$). We write
$G_{1}=G\setminus\overline{N}_{G}(v)$ and $G_{2}=G\setminus\\{v,w\\}$. Then,
$G_{1},G_{2}$ are forests such that $|V(G_{1})|\leq n-1$, $|V(G_{2})|\leq
n-1$.

Since $G_{1}=G\setminus\overline{N}_{G}(v)$ is not empty, it follows from
Theorem 3.1 that

$\displaystyle I({G}[{H}])\simeq$ $\displaystyle\Sigma
I({G_{1}}[{H}])\vee\left(I({G_{1}}[{H}])*I(H)\right)\vee\left(I({G_{2}}[{H}])*I(H)\right).$

By the assumption of the induction, $I({G_{1}}[{H}])$ and $I({G_{2}}[{H}])$
are homotopy equivalent to a wedge sum of spheres or a disjoint union of two
wedge sums of spheres. Therefore, by Lemma 3.6, $I({G}[{H}])$ is homotopy
equivalent to a wedge sum of spheres. So, the proof is completed. ∎

######  Remark 3.7.

For a graph $H$, suppose that $I(H)$ is contractible. Then, for a forest $G$,
we have $I({G}[{H}])\simeq I(G)$. We can prove this fact in the same way as in
the proof of Theorem 1.2.

######  Example 3.8.

Recall that a graph $G$ is chordal if it contains no cycle of length at least
$4$. Kawamura [12, Theorem 1.1] proved that the independence complex of a
chordal graph is either contractible or homotopy equivalent to a wedge sum of
spheres. In particular, Ehrenborg and Hetyei [6, Corollary 6.1] proved that
the independence complex of a forest is either contractible or homotopy
equivalent to a single sphere. So, it follows from Theorem 1.2 and Remark 3.7
that $I({G}[{H}])$ is either contractible or homotopy equivalent to a wedge
sum of spheres if $G$ is a forest and $H$ is a chordal graph.

##  4\. Explicit Calculations

In this section, we offer two examples of explicit calculations on
$I({G}[{H}])$. First, we prove Theorem 1.3.

###### Proof of Theorem 1.3.

For $m=1,2,3$, it follows from Proposition 2.1 that

$\displaystyle I({L_{1}}[{H}])$ $\displaystyle=I(H)\simeq{\bigvee}_{n}S^{k},$
$\displaystyle I({L_{2}}[{H}])$ $\displaystyle=I(H)\sqcup
I(H)\simeq\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}S^{k}\right),$
$\displaystyle I({L_{3}}[{H}])$ $\displaystyle=I(H)\sqcup(I(H)*I(H))$
$\displaystyle\simeq\left({\bigvee}_{n}S^{k}\right)\sqcup\left(\left({\bigvee}_{n}S^{k}\right)*\left({\bigvee}_{n}S^{k}\right)\right)$
$\displaystyle\simeq\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}\left(S^{k}*\left({\bigvee}_{n}S^{k}\right)\right)\right)$
$\displaystyle\simeq\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}\left({\bigvee}_{n}S^{k}*S^{k}\right)\right)$
$\displaystyle\simeq\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n^{2}}S^{2k+1}\right).$

For $r\geq 1$, let $G=L_{r+3}$ and $v=r+2,w=r+3\in V(L_{r+3})$. Then we have
$N_{G}(w)=\\{v\\}$ and $G\setminus\overline{N}_{G}(v)=L_{r}\neq\emptyset$. So,
by Theorem 3.1, we obtain

$\displaystyle I({L_{r+3}}[{H}])$ $\displaystyle\simeq$ $\displaystyle\Sigma
I({L_{r}}[{H}])\vee\left(I({L_{r}}[{H}])*I(H)\right)\
\vee\left(I({L_{r+1}}[{H}])*I(H)\right)$ $\displaystyle\simeq$
$\displaystyle\Sigma
I({L_{r}}[{H}])\vee\left(I({L_{r}}[{H}])*\left({\bigvee}_{n}S^{k}\right)\right)\
\vee\left(I({L_{r+1}}[{H}])*\left({\bigvee}_{n}S^{k}\right)\right)$
$\displaystyle\simeq$ $\displaystyle\Sigma
I({L_{r}}[{H}])\vee\left({\bigvee}_{n}I({L_{r}}[{H}])*S^{k}\right)\vee\left({\bigvee}_{n}I({L_{r+1}}[{H}])*S^{k}\right)$
$\displaystyle\simeq$ $\displaystyle\Sigma
I({L_{r}}[{H}])\vee\left({\bigvee}_{n}\Sigma^{k+1}I({L_{r}}[{H}])\right)\vee\left({\bigvee}_{n}\Sigma^{k+1}I({L_{r+1}}[{H}])\right).$
(1)

Define a CW complex $X_{m,n,k}$ for $m\geq 1$, $n\geq 1$ and $k\geq 0$ by

$\displaystyle X_{m,n,k}=\bigvee_{d\geq 0}\left(\bigvee_{p\geq
0}\left({\bigvee}_{N_{m,n,k}(p,d)}S^{d}\right)\right),$

where

$\displaystyle N_{m,n,k}(p,d)$
$\displaystyle=n^{p}\binom{d-pk+1}{p}\binom{p+1}{3(d-pk+1)-m}.$

We note that $N_{m,n,k}(p,d)>0$ for non-negative integers $p,d$ if and only if
$d-pk+1\geq p$ and $p+1\geq 3(d-pk+1)-m\geq 0$, namely

$\displaystyle pk-1+\max\left\\{p,\frac{m}{3}\right\\}\leq d\leq
pk+\frac{m+p-2}{3}.$

The above inequality implies that $p\leq\frac{m+1}{2}$. So, it follows that

$\displaystyle X_{m,n,k}=\bigvee_{0\leq
p\leq\frac{m+1}{2}}\left(\bigvee_{pk-1+\max\left\\{p,\frac{m}{3}\right\\}\leq
d\leq pk+\frac{m+p-2}{3}}\left({\bigvee}_{N_{m,n,k}(p,d)}S^{d}\right)\right).$

In order to complete the proof, it is sufficient to show that
$I({L_{m}}[{H}])\simeq X_{m,n,k}$ for $m\geq 4$. First, the explicit
descriptions of $X_{1,n,k}$, $X_{2,n,k}$ and $X_{3,n,k}$ are obtained as
follows.

$\displaystyle X_{1,n,k}=$ $\displaystyle\bigvee_{0\leq p\leq
1}\left(\bigvee_{pk-1+\max\left\\{p,\frac{1}{3}\right\\}\leq d\leq
pk+\frac{1+p-2}{3}}\left({\bigvee}_{N_{1,n,k}(p,d)}S^{d}\right)\right)$
$\displaystyle=$
$\displaystyle\bigvee_{p=0,1}\left(\bigvee_{pk-1+\max\left\\{p,\frac{1}{3}\right\\}\leq
d\leq pk+\frac{p-1}{3}}\left({\bigvee}_{N_{1,n,k}(p,d)}S^{d}\right)\right)$
$\displaystyle=$ $\displaystyle\left(\bigvee_{-\frac{2}{3}\leq
d\leq-\frac{1}{3}}\left({\bigvee}_{N_{1,n,k}(0,d)}S^{d}\right)\right)\vee\left(\bigvee_{k\leq
d\leq k}\left({\bigvee}_{N_{1,n,k}(1,d)}S^{d}\right)\right)$ $\displaystyle=$
$\displaystyle{\bigvee}_{N_{1,n,k}(1,k)}S^{k}$ $\displaystyle=$
$\displaystyle{\bigvee}_{n^{1}\binom{1}{1}\binom{2}{2}}S^{k}$ $\displaystyle=$
$\displaystyle{\bigvee}_{n}S^{k}.$ $\displaystyle X_{2,n,k}=$
$\displaystyle\bigvee_{0\leq
p\leq\frac{3}{2}}\left(\bigvee_{pk-1+\max\left\\{p,\frac{2}{3}\right\\}\leq
d\leq pk+\frac{2+p-2}{3}}\left({\bigvee}_{N_{2,n,k}(p,d)}S^{d}\right)\right)$
$\displaystyle=$
$\displaystyle\bigvee_{p=0,1}\left(\bigvee_{pk-1+\max\left\\{p,\frac{2}{3}\right\\}\leq
d\leq pk+\frac{p}{3}}\left({\bigvee}_{N_{2,n,k}(p,d)}S^{d}\right)\right)$
$\displaystyle=$ $\displaystyle\left(\bigvee_{-\frac{1}{3}\leq d\leq
0}\left({\bigvee}_{N_{2,n,k}(0,d)}S^{d}\right)\right)\vee\left(\bigvee_{k\leq
d\leq k+\frac{1}{3}}\left({\bigvee}_{N_{2,n,k}(1,d)}S^{d}\right)\right)$
$\displaystyle=$
$\displaystyle\left({\bigvee}_{N_{2,n,k}(0,0)}S^{0}\right)\vee\left({\bigvee}_{N_{2,n,k}(1,k)}S^{k}\right)$
$\displaystyle=$
$\displaystyle\left({\bigvee}_{n^{0}\binom{1}{0}\binom{1}{1}}S^{0}\right)\vee\left({\bigvee}_{n^{1}\binom{1}{1}\binom{2}{1}}S^{k}\right)$
$\displaystyle=$ $\displaystyle S^{0}\vee\left({\bigvee}_{2n}S^{k}\right).$
$\displaystyle X_{3,n,k}=$ $\displaystyle\bigvee_{0\leq p\leq
2}\left(\bigvee_{pk-1+\max\left\\{p,1\right\\}\leq d\leq
pk+\frac{3+p-2}{3}}\left({\bigvee}_{N_{3,n,k}(p,d)}S^{d}\right)\right)$
$\displaystyle=$
$\displaystyle\bigvee_{p=0,1,2}\left(\bigvee_{pk-1+\max\left\\{p,1\right\\}\leq
d\leq pk+\frac{p+1}{3}}\left({\bigvee}_{N_{3,n,k}(p,d)}S^{d}\right)\right)$
$\displaystyle=$ $\displaystyle\left(\bigvee_{0\leq
d\leq\frac{1}{3}}\left({\bigvee}_{N_{3,n,k}(0,d)}S^{d}\right)\right)\vee\left(\bigvee_{k\leq
d\leq k+\frac{2}{3}}\left({\bigvee}_{N_{3,n,k}(1,d)}S^{d}\right)\right)$
$\displaystyle\ \vee\left(\bigvee_{2k+1\leq d\leq
2k+1}\left({\bigvee}_{N_{3,n,k}(2,d)}S^{d}\right)\right)$ $\displaystyle=$
$\displaystyle\left({\bigvee}_{N_{3,n,k}(0,0)}S^{0}\right)\vee\left({\bigvee}_{N_{3,n,k}(1,k)}S^{k}\right)$
$\displaystyle\ \vee\left({\bigvee}_{N_{3,n,k}(2,2k+1)}S^{2k+1}\right)$
$\displaystyle=$
$\displaystyle\left({\bigvee}_{n^{0}\binom{1}{0}\binom{1}{0}}S^{0}\right)\vee\left({\bigvee}_{n^{1}\binom{1}{1}\binom{2}{0}}S^{k}\right)\vee\left({\bigvee}_{n^{2}\binom{2}{2}\binom{3}{3}}S^{2k+1}\right)$
$\displaystyle=$ $\displaystyle
S^{0}\vee\left({\bigvee}_{n}S^{k}\right)\vee\left({\bigvee}_{n^{2}}S^{2k+1}\right).$

We next show that

$\displaystyle X_{m+3,n,k}=\Sigma
X_{m,n,k}\vee\left({\bigvee}_{n}\Sigma^{k+1}X_{m,n,k}\right)\vee\left({\bigvee}_{n}\Sigma^{k+1}X_{m+1,n,k}\right).$
(2)

We have

$\displaystyle\sum_{p\geq 0}\left(N_{m,n,k}(p,d-1)+n\cdot
N_{m,n,k}(p,d-k-1)+n\cdot N_{m+1,n,k}(p,d-k-1)\right)$ $\displaystyle=$
$\displaystyle\sum_{p\geq
0}\left(n^{p}\binom{(d-1)-pk+1}{p}\binom{p+1}{3((d-1)-pk+1)-m}\right.$
$\displaystyle\ +n^{p+1}\binom{(d-k-1)-pk+1}{p}\binom{p+1}{3((d-k-1)-pk+1)-m}$
$\displaystyle\
\left.+n^{p+1}\binom{(d-k-1)-pk+1}{p}\binom{p+1}{3((d-k-1)-pk+1)-(m+1)}\right)$
$\displaystyle=$ $\displaystyle\sum_{p\geq
0}\left(n^{p}\binom{d-pk}{p}\binom{p+1}{3(d-pk)-m}\right.$ $\displaystyle\
+n^{p+1}\binom{d-(p+1)k}{p}\binom{p+1}{3(d-(p+1)k)-m}$ $\displaystyle\
\left.+n^{p+1}\binom{d-(p+1)k}{p}\binom{p+1}{3(d-(p+1)k)-(m+1)}\right)$
$\displaystyle=$ $\displaystyle\sum_{p\geq
0}n^{p}\binom{d-pk}{p}\binom{p+1}{3(d-pk)-m}$ $\displaystyle\ +\sum_{p\geq
0}n^{p+1}\binom{d-(p+1)k}{p}\binom{p+2}{3(d-(p+1)k)-(m+1)}$ $\displaystyle=$
$\displaystyle\sum_{p\geq 0}n^{p}\binom{d-pk}{p}\binom{p+1}{3(d-pk)-m}$
$\displaystyle\ +\sum_{q=p+1\geq
1}n^{q}\binom{d-qk}{q-1}\binom{q+1}{3(d-qk)-m}$ $\displaystyle=$
$\displaystyle\sum_{p\geq 0}n^{p}\binom{d-pk+1}{p}\binom{p+1}{3(d-pk)-m}$
$\displaystyle=$ $\displaystyle\sum_{p\geq 0}N_{m+3,k}(p,d).$

So, we conclude that

$\displaystyle\Sigma
X_{m,n,k}\vee\left({\bigvee}_{n}\Sigma^{k+1}X_{m,n,k}\right)\vee\left({\bigvee}_{n}\Sigma^{k+1}X_{m+1,n,k}\right)$
$\displaystyle=$ $\displaystyle\bigvee_{d\geq 0}\left(\bigvee_{p\geq
0}\left({\bigvee}_{N_{m,n,k}(p,d-1)+n\cdot N_{m,n,k}(p,d-k-1)+n\cdot
N_{m+1,n,k}(p,d-k-1)}S^{d}\right)\right)$ $\displaystyle=$
$\displaystyle\bigvee_{d\geq 0}\left({\bigvee}_{\sum_{p\geq
0}\left(N_{m,n,k}(p,d-1)+n\cdot N_{m,n,k}(p,d-k-1)+n\cdot
N_{m+1,n,k}(p,d-k-1)\right)}S^{d}\right)$ $\displaystyle=$
$\displaystyle\bigvee_{d\geq 0}\left({\bigvee}_{\sum_{p\geq
0}N_{m+3,n,k}(p,d)}S^{d}\right)$ $\displaystyle=$ $\displaystyle\bigvee_{d\geq
0}\left(\bigvee_{p\geq
0}\left({\bigvee}_{N_{m+3,n,k}(p,d)}S^{d}\right)\right)$ $\displaystyle=$
$\displaystyle X_{m+3,n,k}$

as desired.

Now, we are ready to finish the proof by induction on $m$. By Lemma 3.5, we
obtain

$\displaystyle\Sigma I({L_{2}}[{H}])$
$\displaystyle\simeq\Sigma\left(\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}S^{k}\right)\right)$
$\displaystyle\simeq
S^{1}\vee\Sigma\left({\bigvee}_{n}S^{k}\right)\vee\Sigma\left({\bigvee}_{n}S^{k}\right)$
$\displaystyle\simeq
S^{1}\vee\left({\bigvee}_{n}S^{k+1}\right)\vee\left({\bigvee}_{n}S^{k+1}\right)$
$\displaystyle=S^{1}\vee\left({\bigvee}_{2n}S^{k+1}\right),$
$\displaystyle\Sigma I({L_{3}}[{H}])$
$\displaystyle\simeq\Sigma\left(\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n^{2}}S^{2k+1}\right)\right)$
$\displaystyle\simeq
S^{1}\vee\Sigma\left({\bigvee}_{n}S^{k}\right)\vee\Sigma\left({\bigvee}_{n^{2}}S^{2k+1}\right)$
$\displaystyle\simeq
S^{1}\vee\left({\bigvee}_{n}S^{k+1}\right)\vee\left({\bigvee}_{n^{2}}S^{2k+2}\right).$

So, it follows that

$\displaystyle\Sigma I({L_{m}}[{H}])\simeq\Sigma X_{m,n,k}$

for $m=1,2,3$. Assume that $\Sigma I({L_{r}}[{H}])\simeq\Sigma X_{r,n,k}$ and
$\Sigma I({L_{r+1}}[{H}])\simeq\Sigma X_{r+1,n,k}$ for some $r\geq 1$. By
recursive relations (1) and (2), we have

$\displaystyle I({L_{r+3}}[{H}])$ $\displaystyle\simeq$ $\displaystyle\Sigma
I({L_{r}}[{H}])\vee\left({\bigvee}_{n}\Sigma^{k+1}I({L_{r}}[{H}])\right)\vee\left({\bigvee}_{n}\Sigma^{k+1}I({L_{r+1}}[{H}])\right)$
$\displaystyle\simeq$ $\displaystyle\Sigma
X_{r,n,k}\vee\left({\bigvee}_{n}\Sigma^{k+1}X_{r,n,k}\right)\vee\left({\bigvee}_{n}\Sigma^{k+1}X_{r+1,n,k}\right)$
$\displaystyle=$ $\displaystyle X_{r+3,n,k}.$

Therefore, we obtain that $I({L_{m}}[{H}])\simeq X_{m,n,k}$ for any $m\geq 4$
by induction. This is the desired conclusion. ∎

######  Example 4.1.

Kozlov [13, Proposition 5.2] proved that

$\displaystyle I(C_{n})$ $\displaystyle\simeq\left\\{\begin{aligned}
&S^{k-1}\vee S^{k-1}&&(n=3k),\\\ &S^{k-1}&&(n=3k+1),\\\
&S^{k}&&(n=3k+2).\end{aligned}\right.$

Therefore, we can determine the homotopy types of $I({L_{m}}[{C_{n}}])$ for
any $m\geq 1$ and $n\geq 3$ by Theorem 1.3.

Recall that the homological connectivity of a space $X$, denoted by
$\mathrm{conn}_{H}(X)$, is defined by

$\displaystyle\mathrm{conn}_{H}(X)=\left\\{\begin{aligned}
&-2&&(X=\emptyset),\\\ &k&&(\widetilde{H}_{i}(X)=0\text{ for any $i\leq k$,
}\widetilde{H}_{k+1}(X)\neq 0),\\\ &\infty&&(\widetilde{H}_{i}(X)=0\text{ for
any $i$ }),\end{aligned}\right.$

where $\widetilde{H}_{i}(X)$ is the reduced $i$th homology group of $X$.
Though Theorem 1.3 completely determines the homotopy type of
$I({L_{m}}[{H}])$ with $I(H)\simeq{\bigvee}_{n}S^{k}$, it is hard to obtain
the homological connectivity of $I({L_{m}}[{H}])$ immediately from Theorem
1.3. Here we compute the homological connectivity of $I({L_{m}}[{H}])$ as a
corollary.

######  Corollary 4.2.

Let $H$ be a graph such that $I(H)\simeq{\bigvee}_{n}S^{k}$ with $n\geq 1$,
$k\geq 0$. Then we have

$\displaystyle\mathrm{conn}_{H}(I({L_{3l+i}}[{H}]))=\left\\{\begin{aligned}
&l-2&&(i=0),\\\ &k+l-1&&(i=1),\\\ &l-1&&(i=2).\end{aligned}\right.$

###### Proof.

Recall from the proof of Theorem 1.3 that there is a recursive relation

$\displaystyle I({L_{m+3}}[{H}])$ $\displaystyle\simeq$ $\displaystyle\Sigma
I({L_{m}}[{H}])\vee\left({\bigvee}_{n}\Sigma^{k+1}I({L_{m}}[{H}])\right)\vee\left({\bigvee}_{n}\Sigma^{k+1}I({L_{m+1}}[{H}])\right).$

So, we obtain

$\displaystyle\mathrm{conn}_{H}(I({L_{m+3}}[{H}]))$ $\displaystyle=$
$\displaystyle\min\left\\{\mathrm{conn}_{H}(\Sigma
I({L_{m}}[{H}])),\mathrm{conn}_{H}(\Sigma^{k+1}I({L_{m+1}}[{H}]))\right\\}.$

The base cases are

$\displaystyle\mathrm{conn}_{H}(I({L_{1}}[{H}]))$
$\displaystyle=\mathrm{conn}_{H}\left({\bigvee}_{n}S^{k}\right)=k-1,$
$\displaystyle\mathrm{conn}_{H}(I({L_{2}}[{H}]))$
$\displaystyle=\mathrm{conn}_{H}\left(\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n}S^{k}\right)\right)=-1,$
$\displaystyle\mathrm{conn}_{H}(I({L_{3}}[{H}]))$
$\displaystyle=\mathrm{conn}_{H}\left(\left({\bigvee}_{n}S^{k}\right)\sqcup\left({\bigvee}_{n^{2}}S^{2k+1}\right)\right)=-1.$

Therefore, we can prove the corollary by induction. ∎

We move on to the second example. We denote the complete graph on $n$ vertices
by $K_{n}$. For $n\geq 2$, it is obvious that

$\displaystyle I(K_{n})={\bigvee}_{n-1}S^{0}.$

As the second example in this section, we show that the homological
connectivity of $I({G}[{K_{n}}])$ for any forest $G$ is determined by the
independent domination number of $G$ when $n\geq 2$. For a graph $G$ and a
subset $S\subset V(G)$, $S$ is a dominating set of $G$ if $V(G)=\bigcup_{u\in
S}\overline{N}_{G}(u)$. The domination number $\gamma(G)$ of $G$ is the
minimum cardinality of a dominating set of $G$. The relationship between the
domination number of $G$ and the homological connectivity of $I(G)$ was argued
by Meshulam [14], who proved that for a chordal graph $G$, $i<\gamma(G)$
implies $\widetilde{H}_{i-1}(I(G))=0$ ([14, Theorem 1.2 (iii)]). This is
equivalent to state that $\mathrm{conn}_{H}(I(G))\geq\gamma(G)-2$. This
theorem can be used to deduce a result of Aharoni, Berger and Ziv [2].

A dominating set $S$ of $G$ is called an independent dominating set if $S$ is
an independent set. The independent domination number $i(G)$ is the minimum
cardinality of an independent dominating set of $G$. It is obvious that
$i(G)\geq\gamma(G)$ since an independent dominating set is a dominating set.

######  Theorem 4.3.

Let $G$ be a forest. Then, for any $n\geq 2$, we have

$\displaystyle\mathrm{conn}_{H}(I({G}[{K_{n}}]))=i(G)-2.$ (3)

###### Proof.

We first consider two cases.

  * •

If $G\setminus\overline{N}_{G}(v)=\emptyset$ for some $v\in V(G)$, then we
have $i(G)=1$ and

$\displaystyle\mathrm{conn}_{H}(I({G}[{K_{n}}]))$
$\displaystyle=\mathrm{conn}_{H}\left(\left({\bigvee}_{n-1}S^{0}\right)\sqcup\left({\bigvee}_{(n-1)^{|V(G)|-1}}S^{|V(G)|-2}\right)\right)$
$\displaystyle=-1$

by Theorem 3.1.

  * •

If $G$ has no edges, then we have $i(G)=|V(G)|$ and

$\displaystyle\mathrm{conn}_{H}(I({G}[{K_{n}}]))$
$\displaystyle=\mathrm{conn}_{H}\left({\bigvee}_{(n-1)^{|V(G)|}}S^{|V(G)|-1}\right)$
$\displaystyle=|V(G)|-2.$

Therefore, equation (3) holds in these two cases.

We prove the theorem by induction on $|V(G)|$. Since $L_{1}$, $L_{2}$ and
$L_{1}\sqcup L_{1}$ are included in the above two cases, equation (3) holds
for $G$ such that $|V(G)|\leq 2$. Assume that (3) holds for any forest
$G^{\prime}$ such that $|V(G^{\prime})|\leq r$ with $r\geq 2$. Let $G$ be a
forest such that $|V(G)|=r+1$ and there exists $v,w\in V(G)$ such that
$N_{G}(w)=\\{v\\}$ and $G\setminus\overline{N}_{G}(v)\neq\emptyset$. By
Theorem 3.1, we obtain

$\displaystyle I({G}[{K_{n}}])\simeq$ $\displaystyle\Sigma
I({(G\setminus\overline{N}_{G}(v))}[{K_{n}}])\vee\left(I({(G\setminus\overline{N}_{G}(v))}[{K_{n}}])*\left({\bigvee}_{n-1}S^{0}\right)\right)$
$\displaystyle\
\vee\left(I({(G\setminus\\{v,w\\})}[{K_{n}}])*\left({\bigvee}_{n-1}S^{0}\right)\right)$
$\displaystyle\simeq$ $\displaystyle\Sigma
I({(G\setminus\overline{N}_{G}(v))}[{K_{n}}])\vee\left({\bigvee}_{n-1}\Sigma
I({(G\setminus\overline{N}_{G}(v))}[{K_{n}}])\right)$ $\displaystyle\
\vee\left({\bigvee}_{n-1}\Sigma I({(G\setminus\\{v,w\\})}[{K_{n}}])\right)$
$\displaystyle=$ $\displaystyle\left({\bigvee}_{n}\Sigma
I({(G\setminus\overline{N}_{G}(v))}[{K_{n}}])\right)\vee\left({\bigvee}_{n-1}\Sigma
I({(G\setminus\\{v,w\\})}[{K_{n}}])\right).$

Hence, we get

$\displaystyle\mathrm{conn}_{H}(I({G}[{K_{n}}]))$ $\displaystyle=$
$\displaystyle\min\left\\{\mathrm{conn}_{H}(I({(G\setminus\overline{N}_{G}(v))}[{K_{n}}]))+1,\mathrm{conn}_{H}(I({(G\setminus\\{v,w\\})}[{K_{n}}]))+1\right\\}.$

$G\setminus\overline{N}_{G}(v)$ and $G\setminus\\{v,w\\}$ are the forests
which satisfy $|V(G\setminus\overline{N}_{G}(v))|\leq r-1$,
$|V(G\setminus\\{v,w\\})|\leq r-1$. So, by the assumption of induction, we get

$\displaystyle\mathrm{conn}_{H}(I({G}[{K_{n}}]))=$
$\displaystyle\min\left\\{i(G\setminus\overline{N}_{G}(v))-1,i(G\setminus\\{v,w\\})-1\right\\}.$

Here, we have $i(G\setminus\overline{N}_{G}(v))\geq i(G)-1$. It is because if
there exists an independent dominating set $S$ of
$G\setminus\overline{N}_{G}(v)$ with $|S|<i(G)-1$, then $S\cup\\{v\\}$ is an
independent dominating set of $G$ such that $|S\cup\\{u\\}|<i(G)$, a
contradiction. For the same reason, we also have $i(G\setminus\\{v,w\\})\geq
i(G)-1$.

An independent dominating set of $G$ must contain either $v$ or $w$ since
$N_{G}(w)=\\{v\\}$. If there exists an independent dominating set $S$ of $G$
such that $|S|=i(G)$ and $v\in S$, then $S^{\prime}=S\setminus\\{v\\}$ is an
independent dominating set of $G\setminus\overline{N}_{G}(v)$ with
$|S^{\prime}|=i(G)-1$ since $S\cap\overline{N}_{G}(v)=\\{v\\}$. Thus, in this
case, we obtain $i(G\setminus\overline{N}_{G}(v))=i(G)-1$. If there exists an
independent dominating set $S$ of $G$ such that $|S|=i(G)$ and $w\in S$, then
$S^{\prime\prime}=S\setminus\\{w\\}$ is an independent dominating set of
$G\setminus\\{v,w\\}$ with $|S^{\prime\prime}|=i(G)-1$ since $v\notin S$. So,
in this case, we get $i(G\setminus\\{v,w\\})=i(G)-1$.

Above argument shows that

$\displaystyle\min\left\\{i(G\setminus\overline{N}_{G}(v))-1,i(G\setminus\\{v,w\\})-1\right\\}=i(G)-2.$

Therefore, equation (3) holds for $G$. By induction, we get the desired
conclusion. ∎

## References

  * [1] Michał Adamaszek,  Splittings of independence complexes and the powers of cycles,  Journal of Combinatorial Theory, Series A, 119:1031–1047, 2012\.
  * [2] Ron Aharoni, Eli Berger, and Ran Ziv,  A tree version of Kőnig’s theorem,  Combinatorica, 22(3):335–343, 2002.
  * [3] Jonathan Ariel Barmak,  Star clusters in independence complexes of graphs,  Advances in Mathematics, 241:33–57, 2013.
  * [4] Mireille Bousquet-Mélou, Svante Linusson, and Eran Nevo,  On the independence complex of square grids,  Journal of Algebraic Combinatorics, 27:423–450, 2008.
  * [5] Manoj K. Chari,  On discrete Morse functions and combinatorial decompositions,  Discrete Mathematics, 217:101–113, 2000.
  * [6] Richard Ehrenborg and Gábor Hetyei,  The topology of the independence complex,  European Journal of Combinatorics, 27:906–923, 2006.
  * [7] Alexander Engström,  Complexes of directed trees and independence complexes,  Discrete Mathematics, 309:3299–3309, 2009.
  * [8] Robin Forman,  Morse theory for cell complexes,  Advances in Mathematics, 134:90–145, 1998.
  * [9] Dennis Geller and Saul Stahl,  The chromatic number and other functions of the lexicographic product,  Journal of Combinatorial Theory, Series B, 19:87–95, 1975.
  * [10] Frank Harary,  Graph Theory,  Addison-Wesley Publishing Company, 1969.
  * [11] Kouyemon Iriye,  On the homotopy types of the independence complexes of grid graphs with cylindrical identification,  Kyoto Journal of Mathematics, 52(3):479–501, 2012.
  * [12] Kazuhiro Kawamura,  Independence complexes of chordal graphs,  Discrete Mathematics, 310:2204–2211, 2010.
  * [13] Dmitry N. Kozlov,  Complexes of directed trees,  Journal of Combinatorial theory, Series A, 88:112–122, 1999.
  * [14] Roy Meshulam,  Domination numbers and homology,  Journal of Combinatorial Theory, Series A, 102:321–330, 2003.
  * [15] Johan Thapper,  Independence complexes of cylinders constructed from square and hexagonal grid graphs,  arXiv e-prints, arXiv:0812.1165, 2008.
  * [16] Kevin N. Vander Meulen and Adam Van Tuyl,  Shellability, vertex decomposability, and lexicographical products of graphs,  Contributions to Discrete Mathematics, 12(2):63–68, 2017.