# Certain graphs with exactly one irreducible $T$-module with endpoint $1$,
which is thin: the pseudo-distance-regularized case

Blas Fernández
Andrej Marušič Institute
University of Primorska
Muzejski trg 2, 6000 Koper, Slovenia
<EMAIL_ADDRESS>
###### Abstract

Let $\Gamma$ denote a finite, simple and connected graph. Fix a vertex $x$ of
$\Gamma$ which is not a leaf and let $T=T(x)$ denote the Terwilliger algebra
of $\Gamma$ with respect to $x$. Assume that the unique irreducible $T$-module
with endpoint $0$ is thin, or equivalently that $\Gamma$ is pseudo-distance-
regular around $x$. We consider the property that $\Gamma$ has, up to
isomorphism, a unique irreducible $T$-module with endpoint $1$, and that this
$T$-module is thin. The main result of the paper is a combinatorial
characterization of this property.

Mathematics Subject Classifications: 05C25

Keywords: Terwilliger algebra; irreducible module

##  1 Introduction

Throughout this section, let $\Gamma$ denote a finite, simple and connected
graph. Fix a vertex $x$ of $\Gamma$ which is not a leaf and let $T=T(x)$
denote the Terwilliger algebra of $\Gamma$ with respect to $x$. The algebra
$T$ is non-commutative and semisimple as it is closed under conjugate-
transpose. Therefore, in many instances this algebra can best be studied via
its irreducible modules.

There has been a sizeable amount of research investigating (distance-regular)
graphs that have a Terwilliger algebra $T$ with, up to isomorphism, just a few
$T$-modules of a certain endpoint, all of which are (non-)thin (with respect
to a certain base vertex); see for example [5, 6, 7, 8, 16, 17, 18, 19, 20,
21, 22, 23]. These studies generally try to show that such algebraic
conditions hold if and only if certain combinatorial conditions are satisfied.
A natural follow-up to these results involving Terwilliger algebras of non-
distance-regular graphs is presented here. For the most recent research where
the Terwilliger algebra plays an important role, see for example [1, 12, 13,
14, 15, 24, 27, 28] and the references therein.

It turns out that there exists a unique irreducible $T$-module with endpoint
$0$. It was already proved in [25] that this irreducible $T$-module is thin if
$\Gamma$ is distance-regular around $x$. The converse, however, is not true.
Fiol and Garriga [10] later introduced the concept of pseudo-distance-
regularity around vertex $x$, which is based on assigning weights to the
vertices where the weights correspond to the entries of the (normalized)
positive eigenvector. They showed that the unique irreducible $T$-module with
endpoint $0$ is thin if and only if $\Gamma$ is pseudo-distance-regular around
$x$ (see also [9, Theorem 3.1]). Moreover, Fernández and Miklavič recently
gave a purely combinatorial characterization of the property, that the
irreducible $T$-module with endpoint $0$ is thin (see [8, Theorem 6]). This
characterization involves the number of walks of a certain shape between
vertex $x$ and vertices at some fixed distance from $x$.

Assume that the unique irreducible $T$-module with endpoint $0$ is thin, or
equivalently that $x$ is pseudo-distance-regularized. The main goal of this
paper is to find a combinatorial characterization of graphs, which also have a
unique irreducible $T$-module of endpoint $1$ (up to isomorphism), and this
module is thin. If $\Gamma$ is distance-regular, then this situation occurs if
and only if $\Gamma$ is bipartite or almost-bipartite [4, Theorem 1.3]. If
$\Gamma$ is distance-biregular, then again $\Gamma$ has (up to isomorphism) a
unique irreducible $T$-module with endpoint $1$, and this module is thin (see
[6]). The case when $\Gamma$ is distance-regular around $x$ but not
necessarily distance-regularized (distance-regular or distance-biregular) was
recently considered in [5, 7]. Here we generalize the above results to the
case when $\Gamma$ is not necessarily distance-regular around $x$ and thus
solve [7, Problem 9.1]. The main result of the paper is a combinatorial
characterization of such graphs that involves the number of some walks in
$\Gamma$ of a particular shape. Moreover, we give examples of graphs that
possess the above mentioned combinatorial properties. We remark that this
paper is a generalization of previous efforts in [2, 3, 4, 5, 6, 7] to
understand and classify graphs which are pseudo-distance-regular around a
fixed vertex and also have a unique irreducible $T$-module (up to isomorphism)
with endpoint 1, and this module is thin.

Our paper is organized as follows. In Section 2 we recall basic definitions
and results about Terwilliger algebras that we will find useful later in the
paper. In Section 3 we then state our main result in Theorem 3.5. In Section
4, we prove that certain matrices of the Terwilliger algebra are linearly
dependent, and we use this in Section 5 to prove the main result. In Section
6, we have some comments about certain distance partitions of graphs which are
pseudo-distance-regular around a fixed vertex and also have a unique
irreducible $T$-module (up to isomorphism) with endpoint 1, and this module is
thin. We finish the article presenting some examples in Section 7.

##  2 Preliminaries

In this section we review some definitions and basic concepts. Throughout this
paper, $\Gamma=(X,{\cal R})$ will denote a finite, undirected, connected
graph, without loops and multiple edges, with vertex set $X$ and edge set
${\cal R}$.

Let $x,y\in X$. The distance between $x$ and $y$, denoted by $\partial(x,y)$,
is the length of a shortest $xy$-path. The eccentricity of $x$, denoted by
$\epsilon(x)$, is the maximum distance between $x$ and any other vertex of
$\Gamma$: $\epsilon(x)=\max\\{\partial(x,z)\mid z\in X\\}$. Let $D$ denote the
maximum eccentricity of any vertex in $\Gamma$. We call $D$ the diameter of
$\Gamma$. For an integer $i$ we define $\Gamma_{i}(x)$ by

$\Gamma_{i}(x)=\left\\{y\in X\mid\partial(x,y)=i\right\\}.$

We will abbreviate $\Gamma(x)=\Gamma_{1}(x)$. Note that $\Gamma(x)$ is the set
of neighbours of $x$. Observe that $\Gamma_{i}(x)$ is empty if and only if
$i<0$ or $i>\epsilon(x)$.

We now recall some definitions and basic results concerning a Terwilliger
algebra of $\Gamma$. Let ${\mathbb{C}}$ denote the complex number field. Let
$\operatorname{Mat}_{X}({\mathbb{C}})$ denote the ${\mathbb{C}}$-algebra
consisting of all matrices whose rows and columns are indexed by $X$ and whose
entries are in ${\mathbb{C}}$. Let $V$ denote the vector space over
${\mathbb{C}}$ consisting of column vectors whose coordinates are indexed by
$X$ and whose entries are in ${\mathbb{C}}$. We observe
$\operatorname{Mat}_{X}({\mathbb{C}})$ acts on $V$ by left multiplication. We
call $V$ the standard module. We endow $V$ with the Hermitian inner product
$\langle\,,\,\rangle$ that satisfies $\langle u,v\rangle=u^{\top}\overline{v}$
for $u,v\in V$, where $\top$ denotes transpose and $\overline{\phantom{v}}$
denotes complex conjugation. For $y\in X$, let $\widehat{y}$ denote the
element of $V$ with a $1$ in the ${y}$-coordinate and $0$ in all other
coordinates. We observe $\\{\widehat{y}\;|\;y\in X\\}$ is an orthonormal basis
for $V$.

Let $A\in\operatorname{Mat}_{X}({\mathbb{C}})$ denote the adjacency matrix of
$\Gamma$:

$\left(A\right)_{xy}=\begin{cases}\hskip 5.69046pt1\hskip
14.22636pt\text{if}&\partial(x,y)=1,\\\ \hskip 5.69046pt0\hskip
14.22636pt\text{if}&\partial(x,y)\neq 1,\end{cases}\qquad(x,y\in X).$

The adjacency algebra of $\Gamma$ is a commutative subalgebra $M$ of
$\operatorname{Mat}_{X}({\mathbb{C}})$ generated by the adjacency matrix $A$
of $\Gamma$.

We now recall the dual idempotents of $\Gamma$. To do this fix a vertex $x\in
X$ and let $d=\epsilon(x)$. We view $x$ as a base vertex. For $0\leq i\leq d$,
let $E_{i}^{*}=E_{i}^{*}(x)$ denote the diagonal matrix in
$\operatorname{Mat}_{X}({\mathbb{C}})$ with $(y,y)$-entry as follows:

$\displaystyle(E^{*}_{i})_{yy}=\left\\{\begin{array}[]{lll}1&\hbox{if
}\;\partial(x,y)=i,\\\ 0&\hbox{if }\;\partial(x,y)\neq
i\end{array}\right.\qquad(y\in X).$

We call $E^{*}_{i}$ the $i$-th dual idempotent of $\Gamma$ with respect to $x$
[26, p. 378]. We also observe (ei) $\sum_{i=0}^{d}E_{i}^{*}=I$; (eii)
$\overline{E_{i}^{*}}=E_{i}^{*}$ $(0\leq i\leq d)$; (eiii)
$E_{i}^{*\top}=E_{i}^{*}$ $(0\leq i\leq d)$; (eiv)
$E_{i}^{*}E_{j}^{*}=\delta_{ij}E_{i}^{*}$ $(0\leq i,j\leq d)$ where $I$
denotes the identity matrix in $\operatorname{Mat}_{X}({\mathbb{C}})$. By
these facts, matrices $E_{0}^{*},E_{1}^{*},\ldots,E_{d}^{*}$ form a basis for
a commutative subalgebra $M^{*}=M^{*}(x)$ of
$\operatorname{Mat}_{X}({\mathbb{C}})$. Note that for $0\leq i\leq d$ we have

$E^{*}_{i}V={\rm Span}\\{\widehat{y}\mid y\in\Gamma_{i}(x)\\},$ (2.0.2)

and that

$V=E_{0}^{*}V+E_{1}^{*}V+\cdots+E_{d}^{*}V\qquad\qquad{\rm(orthogonal\ direct\
sum}).$

We call $E^{*}_{i}V$ the $i$-th subconstituent of $\Gamma$ with respect to
$x$. Moreover $E^{*}_{i}$ is the projection from $V$ onto $E^{*}_{i}V$ for
$0\leq i\leq d$. For convenience we define $E^{*}_{-1}$ and $E^{*}_{d+1}$ to
be the zero matrix of $\operatorname{Mat}_{X}({\mathbb{C}})$.

We next recall the definition of a Terwilliger algebra of $\Gamma$ which was
first studied in [26]. Let $T=T(x)$ denote the subalgebra of
$\operatorname{Mat}_{X}({\mathbb{C}})$ generated by $M$, $M^{*}$. We call $T$
the Terwilliger algebra of $\Gamma$ with respect to $x$. Recall $M$ is
generated by $A$ so $T$ is generated by $A$ and the dual idempotents. We
observe $T$ has finite dimension. In addition, by construction $T$ is closed
under the conjugate-transpose map and so $T$ is semi-simple. For a vector
subspace $W\subseteq V$, we denote by $TW$ the subspace $\\{Bw\mid B\in T,w\in
W\\}$.

We now recall the lowering, the flat and the raising matrix of $T$.

######  Definition 2.1.

Let $\Gamma=(X,{\cal R})$ denote a simple, connected, finite graph. Pick $x\in
X$. Let $d=\epsilon(x)$ and let $T=T(x)$ be the Terwilliger algebra of
$\Gamma$ with respect to $x$. Define $L=L(x)$, $F=F(x)$ and $R=R(x)$ in
$\operatorname{Mat}_{X}({\mathbb{C}})$ by

$\displaystyle L=\sum_{i=1}^{d}E^{*}_{i-1}AE^{*}_{i},\hskip
28.45274ptF=\sum_{i=0}^{d}E^{*}_{i}AE^{*}_{i},\hskip
28.45274ptR=\sum_{i=0}^{d-1}E^{*}_{i+1}AE^{*}_{i}.$

We refer to $L$, $F$ and $R$ as the lowering, the flat and the raising matrix
with respect to $x$, respectively. Note that $L,F,R\in T$. Moreover,
$F=F^{\top}$, $R=L^{\top}$ and $A=L+F+R$.

Observe that for $y,z\in X$ we have the $(z,y)$-entry of $L$ equals $1$ if
$\partial(z,y)=1$ and $\partial(x,z)=\partial(x,y)-1$, and $0$ otherwise. The
$(z,y)$-entry of $F$ is equal to $1$ if $\partial(z,y)=1$ and
$\partial(x,z)=\partial(x,y)$, and $0$ otherwise. Similarly, the $(z,y)$-entry
of $R$ equals $1$ if $\partial(z,y)=1$ and $\partial(x,z)=\partial(x,y)+1$,
and $0$ otherwise. Consequently, for $v\in E^{*}_{i}V\;(0\leq i\leq d)$ we
have

$Lv\in E^{*}_{i-1}V,\qquad Fv\in E^{*}_{i}V,\qquad Rv\in E^{*}_{i+1}V.$
(2.0.3)

By a $T$-module we mean a subspace $W$ of $V$, such that $TW\subseteq W$. Let
$W$ denote a $T$-module. Then $W$ is said to be irreducible whenever $W$ is
nonzero and $W$ contains no $T$-modules other than $0$ and $W$. Since the
algebra $T$ is semi-simple, it turns out that any $T$-module is an orthogonal
direct sum of irreducible $T$-modules.

Let $W$ be an irreducible $T$-module. We observe that $W$ is an orthogonal
direct sum of the nonvanishing subspaces $E_{i}^{*}W$ for $0\leq i\leq d$. By
the endpoint of $W$ we mean $r:=r(W)=\min\\{i\mid 0\leq i\leq
d,\;E^{*}_{i}W\neq 0\\}$. Define the diameter of $W$ by
$d^{\prime}:=d^{\prime}(W)=\left|\\{i\mid 0\leq i\leq d,\;E^{*}_{i}W\neq
0\\}\right|-1$. Using the idea from [26, Lemma 3.9(ii)] we have
$E^{*}_{i}W\neq 0$ if and only if $r\leq i\leq r+d^{\prime}$ $(0\leq i\leq
d)$. We also say that $W$ is thin whenever the dimension of $E^{*}_{i}W$ is at
most 1 for $0\leq i\leq d$.

Let $W$ and $W^{\prime}$ denote two irreducible $T$-modules. By a
$T$-isomorphism from $W$ to $W^{\prime}$ we mean a vector space isomorphism
$\sigma:W\rightarrow W^{\prime}$ such that $\left(\sigma B-B\sigma\right)W=0$
for all $B\in T$. The $T$-modules $W$ and $W^{\prime}$ are said to be
$T$-isomorphic (or simply isomorphic) whenever there exists a $T$-isomorphism
$\sigma:W\rightarrow W^{\prime}$. We note that isomorphic irreducible
$T$-modules have the same endpoint. It turns out that two non-isomorphic
irreducible $T$-modules are orthogonal.

Observe that the subspace $T\widehat{x}=\\{B\widehat{x}\;|\;B\in T\\}$ is a
$T$-module. Suppose that $W$ is an irreducible $T$-module with endpoint $0$.
Then, $\widehat{x}\in W$, which implies that $T\widehat{x}\subseteq W$. Since
$W$ is irreducible, we therefore have $T\widehat{x}=W$. Hence, $T\widehat{x}$
is the unique irreducible $T$-module with endpoint $0$. We refer to
$T\widehat{x}$ as the trivial $T$-module. If the trivial $T$-module is thin,
then vectors $R^{i}\widehat{x}\;(0\leq i\leq d)$ form a basis of the trivial
$T$-module (see [8] for more details). In the rest of this paper we will study
irreducible $T$-modules of endpoint $1$. Therefore, we will first characterize
those vertices $x$ of $\Gamma$, for which the corresponding Terwilliger
algebra $T=T(x)$ has no irreducible $T$-modules with endpoint $1$.

######  Proposition 2.2.

Let $\Gamma=(X,{\cal R})$ denote a simple, finite, connected graph. Pick a
vertex $x\in X$ and let $T=T(x)$ denote the corresponding Terwilliger algebra.
Then, there are no irreducible $T$-modules with endpoint $1$ if and only if
$\dim(E^{*}_{1}T\widehat{x})=|\Gamma(x)|$. In particular, if the trivial
module is thin, there are no irreducible $T$-modules with endpoint $1$ if and
only if $|\Gamma(x)|=1$.

###### Proof.

Let $V$ denote the standard module, and let $T\widehat{x}$ denote the trivial
$T$-module. We observe $E^{*}_{1}T\widehat{x}\subseteq E^{*}_{1}V$ and so,
$\dim(E^{*}_{1}T\widehat{x})\leq\dim(E^{*}_{1}V)=|\Gamma(x)|.$

Assume first that there are no irreducible $T$-modules with endpoint $1$.
Since $V$ is orthogonal direct sum of irreducible $T$-modules and none of
these $T$-modules has endpoint $1$ we have $E^{*}_{1}V=E^{*}_{1}T\widehat{x}$
which implies that $\dim(E^{*}_{1}T\widehat{x})=\dim(E^{*}_{1}V)=|\Gamma(x)|$.

We next proceed by contraposition. Suppose there exists an irreducible
$T$-module $W$ with endpoint $1$. Let $V_{1}$ be the sum of all irreducible
$T$-modules with endpoint $1$. Note that $E^{*}_{1}W$ is nonzero and since
$E^{*}_{1}W\subseteq E^{*}V_{1}$, we have $\dim(E^{*}_{1}V_{1})>0$. We also
have $E^{*}_{1}V=E^{*}_{1}T\widehat{x}+E^{*}_{1}V_{1}$. This shows that

$|\Gamma(x)|=\dim(E^{*}_{1}V)=\dim(E^{*}_{1}T\widehat{x})+\dim(E^{*}_{1}V_{1})>\dim(E^{*}_{1}T\widehat{x}).$

To prove the second part of our assertion, recall that if $T\widehat{x}$ is
thin, by [8, Lemma 9], the subspace $E^{*}_{1}T\widehat{x}$ is spanned by the
nonzero vector $R\widehat{x}$. This concludes the proof. ∎

In view of Proposition 2.2, we will assume that $|\Gamma(x)|\geq 2$ from now
on.

##  3 The Main Result

Throughout this section let $\Gamma=(X,{\cal R})$ denote a connected graph.
Here we state our main result. To do this we need the following definitions.

We first define a certain partition of $X$ that we will find useful later.

######  Definition 3.1.

Let $\Gamma=(X,{\cal R})$ denote a graph with diameter $D$. Pick $x,y\in X$,
such that $y\in\Gamma(x)$. For integers $i,j$ we define sets
$D^{i}_{j}:=D^{i}_{j}(x,y)$ as follows:

$D^{i}_{j}=\Gamma_{i}(x)\cap\Gamma_{j}(y).$

Observe that $D^{i}_{j}=\emptyset$ if $i<0$ or $j<0$. Similarly,
$D^{i}_{j}=\emptyset$ if $i>\epsilon(x)$ or $j>\epsilon(y)$. Furthermore, by
the triangle inequality we have that $D^{i}_{j}=\emptyset$ if $|i-j|\geq 2$.
Note also that if $\Gamma$ is bipartite, the set $D_{i}^{i}$ is empty for
$0\leq i\leq D$. The collection of all the subsets $D^{i}_{i-1}$ $(1\leq
i\leq\epsilon(x))$, $D^{i}_{i}$ $(1\leq
i\leq\min\left\\{\epsilon(x),\epsilon(y)\right\\})$ and $D_{i}^{i-1}$ $(1\leq
i\leq\epsilon(y))$ is called the distance partition of $\Gamma$ with respect
to the edge $\left\\{x,y\right\\}$.

Next, we consider walks of a certain shape with respect to a given vertex in
$\Gamma$.

######  Definition 3.2.

Let $\Gamma=(X,{\cal R})$ denote a connected graph. Pick $x,y,z\in X$ and let
$P=[y=x_{0},x_{1},\ldots,x_{j}=z]$ denote a $yz$-walk. The shape of $P$ with
respect to $x$ is a sequence of symbols $t_{1}t_{2}\ldots t_{j}$, where
$t_{i}\in\\{f,\ell,r\\}$, and such that $t_{i}=r$ if
$\partial(x,x_{i})=\partial(x,x_{i-1})+1$, $t_{i}=f$ if
$\partial(x,x_{i})=\partial(x,x_{i-1})$ and $t_{i}=\ell$ if
$\partial(x,x_{i})=\partial(x,x_{i-1})-1\;(1\leq i\leq j)$. We use exponential
notation for shapes containing several consecutive identical symbols. For
instance, instead of $rrrrfff\ell\ell r$ we simply write
$r^{4}f^{3}\ell^{2}r$. Analogously, $r^{0}f=f$ and $r^{0}\ell=\ell r^{0}=\ell$
is also conventional. For a non-negative integer $m$, let $\ell r^{m}(y,z)$,
$r^{m}\ell(y,z)$, $r^{m}f(y,z)$ and $r^{m}(y,z)$ respectively denote the
number of $yz$-walks of the shape $\ell r^{m}$, $r^{m}\ell$, $r^{m}f$ and
$r^{m}$ with respect to $x$ where $r^{0}(y,z)=1$ if $y=z$ and $r^{0}(y,z)=0$
otherwise. We abbreviate $r^{m}\ell(z)=r^{m}\ell(x,z)$,
$r^{m}f(z)=r^{m}f(x,z)$ and $r^{m}(z)=r^{m}(x,z)$.

The following observation is straightforward to prove (using elementary matrix
multiplication and (2.0.3)).

######  Lemma 3.3.

Let $\Gamma=(X,{\cal R})$ denote a connected graph. Pick $x\in X$ and let
$T=T(x)$ denote the Terwilliger algebra of $\Gamma$ with respect to $x$. Let
$L=L(x)$, $F=F(x)$ and $R=R(x)$ denote the lowering, the flat and the raising
matrix of $T$, respectively. Pick $y,z\in X$ and let $m$ be a non-negative
integer. Then the following (i)-(iv) hold:

  1. (i)

The $(z,y)$-entry of $R^{m}$ is equal to the number $r^{m}(y,z)$ with respect
to $x$.

  2. (ii)

The $(z,y)$-entry of $LR^{m}$ is equal to the number $r^{m}\ell(y,z)$ with
respect to $x$.

  3. (iii)

The $(z,y)$-entry of $R^{m}L$ is equal to the number $\ell r^{m}(y,z)$ with
respect to $x$.

  4. (iv)

The $(z,y)$-entry of $FR^{m}$ is equal to the number $r^{m}f(y,z)$ with
respect to $x$.

For the rest of the paper we adopt the following notation.

######  Notation 3.4.

Let $\Gamma=(X,{\cal R})$ denote a finite, simple, connected graph with vertex
set $X$, edge set ${\cal R}$ and diameter $D$. Let
$A\in\operatorname{Mat}_{X}({\mathbb{C}})$ denote the adjacency matrix of
$\Gamma$. Fix a vertex $x\in X$ with $|\Gamma(x)|\geq 2$. Let $d$ denote the
eccentricity of $x$. Let
$E^{*}_{i}\in\operatorname{Mat}_{X}({\mathbb{C}})\;(0\leq i\leq d)$ denote the
dual idempotents of $\Gamma$ with respect to $x$. Let $V$ denote the standard
module of $\Gamma$ and let $T=T(x)$ denote the Terwilliger algebra of $\Gamma$
with respect to $x$. Let $L=L(x)$, $F=F(x)$ and $R=R(x)$ denote the lowering,
the flat and the raising matrix of $T$, respectively. Assume that the unique
irreducible $T$-module with endpoint $0$ is thin. We denote this $T$-module by
$T\widehat{x}$. For $y\in\Gamma(x)$ let the sets $D^{i}_{j}=D^{i}_{j}(x,y)$ be
as defined in Definition 3.1. For $w,z\in X$ let the numbers $r^{m}\ell(w,z)$,
$r^{m}f(w,z)$ and $r^{m}(w,z)$ be as defined in Definition 3.2.

We are now ready to state our main result.

######  Theorem 3.5.

With reference to Notation 3.4, the following (i)-(ii) are equivalent:

  1. (i)

$\Gamma$ has, up to isomorphism, a unique irreducible $T$-module with endpoint
$1$, and this module is thin.

  2. (ii)

For every integer $i$ $\;(1\leq i\leq d)$ there exist scalars
$\kappa_{i},\mu_{i}$, $\theta_{i},\rho_{i}$, such that for every
$y\in\Gamma(x)$ the following (a), (b) hold:

    1. (a)

For every $z\in D^{i}_{i+1}(x,y)\cup D^{i}_{i}(x,y)$ we have

$\displaystyle r^{i}\ell(y,z)$ $\displaystyle=$ $\displaystyle\mu_{i}\;\ell
r^{i}(y,z),$ $\displaystyle r^{i-1}f(y,z)$ $\displaystyle=$
$\displaystyle\rho_{i}\;\ell r^{i}(y,z).$

    2. (b)

For every $z\in D^{i}_{i-1}(x,y)$ we have

$\displaystyle r^{i}\ell(y,z)$ $\displaystyle=$
$\displaystyle\kappa_{i}\;r^{i-1}(y,z)+\mu_{i}\;\ell r^{i}(y,z),$
$\displaystyle r^{i-1}f(y,z)$ $\displaystyle=$
$\displaystyle\theta_{i}\;r^{i-1}(y,z)+\rho_{i}\;\ell r^{i}(y,z).$

Moreover, $\rho_{i}=0$ whenever the set $D^{i}_{i+1}(x,y)$ is nonempty for
some $y\in\Gamma(x)$.

With reference to Notation 3.4, assume that $\Gamma$ satisfies part $(ii)$ of
Theorem 3.5. The proof that in this case $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin is omitted as it can be carried out using similar arguments as in the
proof of [5, Theorem 4.4] (see [5, Section 6]). Therefore, in the rest of this
article, we will focus on the proof that part ${(i)}$ of Theorem 3.5 implies
the combinatorial conditions ${(a),(b)}$ described in part ${(ii)}$ of Theorem
3.5.

With reference to Notation 3.4, assume that $\Gamma$ is distance-regular
around $x$ (see [11] for the definition of distance-regularity around a
vertex). In this case, it was proved in [8, 25] that the unique irreducible
$T$-module with endpoint $0$ is thin. In addition, for an integer $i\;(1\leq
i\leq d)$ and vertices $y\in\Gamma(x),z\in\Gamma_{i}(x)$, we observe the
number of $yz$-walks of the shape $\ell r^{i}$ with respect to $x$ is equal to
the number of paths of length $i$ from $z$ to $x$. Since $x$ is distance-
regularized, there are precisely $c_{i}(x)c_{i-1}(x)\cdots c_{1}(x)$ such
paths. Consequently, $\ell r^{i}(y,z)=c_{i}(x)c_{i-1}(x)\cdots c_{1}(x)$ and
so, $\ell r^{i}(y,z)$ is independent of the choice of $y$ and $z$. Therefore,
[5, Theorem 4.4] and [7, Theorem 4.4] immediately follow from Theorem 3.5 and
the above comments.

We finish this section with the following observations which will be needed
later for the proof of Theorem 3.5.

######  Proposition 3.6.

With reference to Notation 3.4, the following holds for $0\leq i\leq d$:

$\displaystyle\left(E_{i}^{*}R^{i}LE_{1}^{*}\right)_{zy}=\left\\{\begin{array}[]{lll}\displaystyle\ell
r^{i}(y,z)\displaystyle&\hbox{if }\;y\in\Gamma(x)\hbox{ and
}z\in\Gamma_{i}(x),\\\ 0&\hbox{otherwise}.\end{array}\right.$ (3.0.3)

In particular, $E_{i}^{*}R^{i}LE_{1}^{*}$ is nonzero.

###### Proof.

It is straightforward to check that the $(z,y)$-entry of
$E^{*}_{i}R^{i}LE^{*}_{1}$ is zero if either $y\not\in\Gamma(x)$ or
$z\not\in\Gamma_{i}(x)$. It is also straightforward to check that the result
is true if $i=0$. Suppose now that $y\in\Gamma(x)$ and $z\in\Gamma_{i}(x)$
with $i\geq 1$. Then
$\left(E_{i}^{*}R^{i}LE_{1}^{*}\right)_{zy}=\left(R^{i}L\right)_{zy}$ and the
result follows from Lemma 3.3. Note also that in this case we have that $\ell
r^{i}(y,z)>0$ and so, $E_{i}^{*}R^{i}LE_{1}^{*}$ is nonzero. ∎

######  Proposition 3.7.

With reference to Notation 3.4, the following holds for $1\leq i\leq d$:

$\displaystyle\left(E_{i}^{*}R^{i-1}E_{1}^{*}\right)_{zy}=\left\\{\begin{array}[]{lll}\displaystyle
r^{i-1}(y,z)\displaystyle&\hbox{if }\;y\in\Gamma(x)\hbox{ and
}z\in\Gamma_{i}(x),\\\ 0&\hbox{otherwise}.\end{array}\right.$ (3.0.6)

In particular, $E_{i}^{*}R^{i-1}E_{1}^{*}$ is nonzero.

###### Proof.

Similar to the proof of Proposition 3.6. ∎

##  4 Linear dependency

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. In this section we show that certain matrices of $T$ are linearly
dependent.

######  Theorem 4.1.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin with diameter $d^{\prime}$. Pick matrices $F_{1},F_{2},F_{3}\in T$ and an
integer $i\;(1\leq i\leq d)$. Then the following (i), (ii) hold:

  1. (i)

For every integer $i\;(1\leq i\leq d^{\prime}+1)$ the matrices
$E_{i}^{*}F_{1}E_{1}^{*}$, $E_{i}^{*}F_{2}E_{1}^{*}$ and
$E_{i}^{*}F_{3}E_{1}^{*}$ are linearly dependent.

  2. (ii)

For every integer $i\;(d^{\prime}+1<i\leq d)$ the matrices
$E_{i}^{*}F_{1}E_{1}^{*}$ and $E_{i}^{*}F_{2}E_{1}^{*}$ are linearly
dependent.

###### Proof.

Recall that $T\widehat{x}$ is thin and by [8, Lemma 9], the subspace
$E^{*}_{1}T\widehat{x}$ is spanned by the nonzero vector $R\widehat{x}$ and
so, $\dim(E^{*}_{1}T\widehat{x})=1$.

Let $W$ be a thin irreducible $T$-module with endpoint $1$ and diameter
$d^{\prime}$. Firstly, we observe that $d^{\prime}+1\leq d$ and so, ${(i)}$
immediately follows from [7, Theorem 5.3]. We would like to point out the same
conclusions of [7, Theorem 5.3] are true without assuming that $\Gamma$ is
bipartite and distance-regular around $x$. Namely, in the proof of [7, Theorem
5.3], the hypothesis that $\Gamma$ is bipartite was never applied and local
distance-regularity around $x$ was used to conclude that
$\dim\left(E^{*}_{1}T\widehat{x}\right)=1$, which is also true in our case.

We now proceed to prove the second assertion. To do that, pick an integer
$i\;(d^{\prime}+1<i\leq d)$. We claim there exist scalars
$\lambda_{1},\lambda_{2}$, not both zero, such that
$\lambda_{1}E_{i}^{*}F_{1}E_{1}^{*}v+\lambda_{2}E_{i}^{*}F_{2}E_{1}^{*}v=0$
for every $v\in E^{*}_{1}T\widehat{x}$. To see this, pick nonzero vectors
$v_{0}\in E^{*}_{1}T\widehat{x}$ and $v_{1}\in E_{1}^{*}W$. Let $u_{0}$ be an
arbitrary nonzero vector of $E^{*}_{i}T\widehat{x}$. As the trivial module is
thin, there exist scalars $r_{0,1}$, $r_{0,2}$ such that

$E_{i}^{*}F_{1}E_{1}^{*}v_{0}=r_{0,1}\,u_{0}\qquad\hbox{and}\qquad
E_{i}^{*}F_{2}E_{1}^{*}v_{0}=r_{0,2}\,u_{0}.$ (4.0.1)

It is clear that the linear equation $r_{0,1}\;x_{1}+r_{0,2}\;x_{2}=0$ with
unknowns $x_{1},x_{2}$ has a nontrivial solution, and so there exist scalars
$\lambda_{1},\lambda_{2}$, not both zero, such that

$r_{0,1}\;\lambda_{1}+r_{0,2}\;\lambda_{2}=0.$ (4.0.2)

Pick a vector $v\in E_{1}^{*}T\widehat{x}$. Since the trivial $T$-module is
thin, there exists a scalar $\lambda$ such that $v=\lambda v_{0}$. Therefore,
by (4.0.1) and (4.0.2) we have

$\displaystyle\lambda_{1}{E_{i}^{*}F_{1}E_{1}^{*}v}+\lambda_{2}{E_{i}^{*}F_{2}E_{1}^{*}v}$
$\displaystyle=$
$\displaystyle\lambda\left(\lambda_{1}{E_{i}^{*}F_{1}E_{1}^{*}v_{0}}+\lambda_{2}{E_{i}^{*}F_{2}E_{1}^{*}v_{0}}\right)$
$\displaystyle=$
$\displaystyle\lambda\left(\lambda_{1}\;r_{0,1}u_{0}+\lambda_{2}\;r_{0,2}u_{0}\right)$
$\displaystyle=$
$\displaystyle\lambda\left(r_{0,1}\;\lambda_{1}+r_{0,2}\;\lambda_{2}\right)u_{0}=0.$

This proves our claim. Let $V_{1}$ denote the sum of all irreducible
$T$-modules with endpoint $1$ and let $\\{W^{t}\mid t\in\mathcal{I}\\}$ be the
set of all irreducible $T$-modules with endpoint $1$, where $\mathcal{I}$ is
an index set. Pick a vector $v\in E_{1}^{*}V_{1}$. Observe that $v$ can be
written as a sum

$v=\sum_{t\in\mathcal{I}}v_{t},$ (4.0.3)

where $v_{t}\in E^{*}_{1}W^{t}$ for every $t\in\mathcal{I}$. Pick now a
$T$-module $W^{s}$, $s\in\mathcal{I}$. As any two irreducible $T$-modules with
endpoint $1$ are isomorphic, it follows that
$d^{\prime}\left(W^{s}\right)=d^{\prime}\left(W\right)=d^{\prime}$. So, we
observe that in this case $E^{*}_{i}W^{s}$ is zero. In addition, for every
$t\in\mathcal{I}$ there exists a $T$-isomorphism $\sigma_{t}:W^{s}\rightarrow
W^{t}$. Let $w_{t}\in W^{s}$ be such that $v_{t}=\sigma_{t}(w_{t})$. Then, we
notice that for every $t\in\mathcal{I}$,

$E_{i}^{*}F_{j}E_{1}^{*}v_{t}=E_{i}^{*}F_{j}E_{1}^{*}\sigma_{t}(w_{t})=\sigma_{t}\left(E_{i}^{*}F_{j}E_{1}^{*}w_{t}\right)=0.$

Hence, by (4.0.3) we have that $E_{i}^{*}F_{j}E_{1}^{*}v=0$ for every $v\in
E_{1}^{*}V_{1}$.

To conclude the proof, pick now an arbitrary vector $w\in V$ and observe that
$E^{*}_{1}w=w_{0}+w_{1}$ for some $w_{0}\in T\widehat{x}$ and $w_{1}\in
V_{1}$. It follows from the above comments that there exist scalars
$\lambda_{1},\lambda_{2}$, not both zero, such that

$\displaystyle\lambda_{1}{E_{i}^{*}F_{1}E_{1}^{*}w}+\lambda_{2}{E_{i}^{*}F_{2}E_{1}^{*}w}$
$\displaystyle=$
$\displaystyle\lambda_{1}{E_{i}^{*}F_{1}E_{1}^{*}(w_{0}+w_{1})}+\lambda_{2}{E_{i}^{*}F_{2}E_{1}^{*}(w_{0}+w_{1})}=0.$

As $w$ was arbitrary, the result follows. ∎

Observe that the conclusion of Theorem 4.1 is equivalent to the fact that the
dimension of $E_{i}^{*}TE_{1}^{*}\;(1\leq i\leq d^{\prime}+1)$ is at most 2
and that the dimension of $E_{i}^{*}TE_{1}^{*}\;(d^{\prime}+1<i\leq d)$ is at
most 1.

##  5 Algebraic condition implies combinatorial properties

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. In this section we prove that in this case combinatorial conditions
${(a),(b)}$ described in part ${(ii)}$ of Theorem 3.5 hold.

######  Lemma 5.1.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. Then for every $i\ (1\leq i\leq d)$ there exist scalars
$\kappa_{i},\mu_{i},\theta_{i},\rho_{i}$, such that

$\displaystyle E^{*}_{i}LR^{i}E^{*}_{1}$ $\displaystyle=$
$\displaystyle\kappa_{i}E^{*}_{i}R^{i-1}E^{*}_{1}+\mu_{i}E^{*}_{i}R^{i}LE^{*}_{1},$
(5.0.1) $\displaystyle E^{*}_{i}FR^{i-1}E^{*}_{1}$ $\displaystyle=$
$\displaystyle\theta_{i}E^{*}_{i}R^{i-1}E^{*}_{1}+\rho_{i}E^{*}_{i}R^{i}LE^{*}_{1}.$
(5.0.2)

###### Proof.

Pick $i\;(1\leq i\leq d)$ and observe that by Definition 2.1, the matrices
$LR^{i}$, $R^{i-1}$, $FR^{i-1}$ and $R^{i}L$ are elements of algebra $T$.
Consequently, by Theorem 4.1, there exist scalars $\alpha_{j}^{(i)}$ $(1\leq
j\leq 3)$, not all zero, and $\beta_{j}^{(i)}$ $(1\leq j\leq 3)$, not all
zero, such that

$\displaystyle\alpha_{1}^{(i)}E_{i}^{*}LR^{i}E_{1}^{*}+\alpha_{2}^{(i)}E_{i}^{*}R^{i-1}E_{1}^{*}+\alpha_{3}^{(i)}E_{i}^{*}R^{i}LE_{1}^{*}=0,$
(5.0.3)
$\displaystyle\beta_{1}^{(i)}E_{i}^{*}FR^{i-1}E_{1}^{*}+\beta_{2}^{(i)}E_{i}^{*}R^{i-1}E_{1}^{*}+\beta_{3}^{(i)}E_{i}^{*}R^{i}LE_{1}^{*}=0.$
(5.0.4)

Assume for the moment that $\alpha_{1}^{(i)}\beta_{1}^{(i)}\neq 0$. Then
(5.0.1) and (5.0.2) hold with $\kappa_{i}=-\alpha_{2}^{(i)}/\alpha_{1}^{(i)}$,
$\mu_{i}=-\alpha_{3}^{(i)}/\alpha_{1}^{(i)}$,
$\theta_{i}=-\beta_{2}^{(i)}/\beta_{1}^{(i)}$, and
$\rho_{i}=-\beta_{3}^{(i)}/\beta_{1}^{(i)}$.

Now, assume that $\alpha_{1}^{(i)}\beta_{1}^{(i)}=0$. Let $W$ denote an
irreducible $T$-module with endpoint $1$. Let $k$ denote the least integer
such that $\alpha_{1}^{(k)}\beta_{1}^{(k)}=0$. We observe $k\leq i$. Assume
for a moment that $k=1$. Without loss of generality assume that
$\alpha_{1}^{(1)}=0$. Pick $y,z\in\Gamma(x)$, $y\neq z$. As the
$(z,y)$-entries of $E^{*}_{1}$ and $E^{*}_{1}RLE^{*}_{1}$ are $0$ and $1$
respectively, (5.0.3) implies that $\alpha_{3}^{(1)}=0$. As $E^{*}_{1}$ is
nonzero, we get that $\alpha_{2}^{(1)}=0$ as well, a contradiction. Therefore,
$k\geq 2$. Pick a nonzero vector $w\in E^{*}_{1}W$ and let $W^{\prime}$ denote
the vector subspace of $V$ spanned by the vectors $R^{i}w\;(0\leq i\leq d)$.
Note $W^{\prime}$ is nonzero and $W^{\prime}\subseteq W$. Observe also that by
(2.0.3) and by (eiv) from Section 2, the subspace $W^{\prime}$ is invariant
under the action of the dual idempotents. Since
$\alpha_{1}^{(k)}\beta_{1}^{(k)}=0$ and by Proposition 3.6 the matrix
$E^{*}_{k}R^{k}LE^{*}_{1}$ is nonzero, it follows from (5.0.3) and (5.0.4)
that there exists $\gamma\in\mathbb{C}$ such that
$E^{*}_{i}R^{k-1}E^{*}_{1}=\gamma E^{*}_{k}R^{k}LE^{*}_{1}$. Now, from (2.0.3)
we notice that $Lw=0$ and so, $R^{k-1}w=0$. This implies
$FR^{j}w=LR^{j}w=R^{j}w=0$ for $k-1\leq j\leq d$. Therefore, by construction
and by (2.0.3), it is also clear that $W^{\prime}$ is closed under the action
of $R$. Moreover, for every $1\leq j\leq k-1$ the scalar
$\alpha_{1}^{(j)}\beta_{1}^{(j)}$ is nonzero. Therefore, from (5.0.3) and
(5.0.4), we have that (5.0.1) and (5.0.2) hold for $1\leq j\leq k-1$ with
$\kappa_{j}=-\alpha_{2}^{(j)}/\alpha_{1}^{(j)}$,
$\mu_{j}=-\alpha_{3}^{(j)}/\alpha_{1}^{(j)}$,
$\theta_{j}=-\beta_{2}^{(j)}/\beta_{1}^{(j)}$, and
$\rho_{j}=-\beta_{3}^{(j)}/\beta_{1}^{(j)}$. So, $LR^{j}w=\kappa_{j}R^{j-1}w$
and $FR^{j-1}w=\theta_{j}R^{j-1}w$ for $1\leq j\leq k-1$. This implies that
$W^{\prime}$ is invariant under the action of $L$ and $F$. Since $A=L+F+R$, it
turns out that $W^{\prime}$ is $A$-invariant as well. Recall that algebra $T$
is generated by $A$ and the dual idempotents. Therefore, $W^{\prime}$ is a
$T$-module and $W^{\prime}=W$ as $W$ is irreducible. Notice that by
construction and (2.0.3), the subspace $E^{*}_{i}W$ is generated by
$R^{i-1}w$. This shows $E^{*}_{i}W=0$ since $k\leq i$. We thus have
$d^{\prime}+1<i\leq d$ where $d^{\prime}$ denotes the diameter of $W$. Hence,
by Theorem 4.1${(ii)}$, any two matrices in $E_{i}^{*}TE_{1}^{*}$ are linearly
dependent. Consequently, there exist scalars $\alpha,\beta$ (not both zero)
and $\alpha^{\prime},\beta^{\prime}$ (not both zero), such that

$\displaystyle\alpha E_{i}^{*}LR^{i}E_{1}^{*}+\beta
E_{i}^{*}R^{i-1}E_{1}^{*}=0,$ (5.0.5)
$\displaystyle\alpha^{\prime}E_{i}^{*}FR^{i-1}E_{1}^{*}+\beta^{\prime}E_{i}^{*}R^{i-1}E_{1}^{*}=0.$
(5.0.6)

If $\alpha$ ($\alpha^{\prime}$, respectively) is zero, then $\beta$
($\beta^{\prime}$, respectively) is also zero by Proposition 3.7, a
contradiction. This shows that
$E_{i}^{*}LR^{i}E_{1}^{*}=-\frac{\beta}{\alpha}E_{i}^{*}R^{i-1}E_{1}^{*}$ and
$E_{i}^{*}FR^{i-1}E_{1}^{*}=-\frac{\beta^{\prime}}{\alpha^{\prime}}E_{i}^{*}R^{i-1}E_{1}^{*}$.
Similarly we show that $E_{i}^{*}R^{i}LE_{1}^{*}=\lambda
E_{i}^{*}R^{i-1}E_{1}^{*}$ for some nonzero scalar $\lambda\in\mathbb{C}$. It
is now clear that (5.0.1) and (5.0.2) hold for any $\kappa_{i},\mu_{i}$,
$\theta_{i},\rho_{i}$ satisfying $\kappa_{i}+\lambda\mu_{i}=-\beta/\alpha$ and
$\theta_{i}+\lambda\rho_{i}=-\beta^{\prime}/\alpha^{\prime}$. This finishes
the proof. ∎

We are now ready to prove the main result of this section.

######  Theorem 5.2.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. For every integer $i$ $\;(1\leq i\leq d)$ there exist scalars
$\kappa_{i},\mu_{i}$, $\theta_{i},\rho_{i}$, such that for every
$y\in\Gamma(x)$ the following (a), (b) hold:

  1. (a)

For every $z\in D^{i}_{i+1}(x,y)\cup D^{i}_{i}(x,y)$ we have

$\displaystyle r^{i}\ell(y,z)$ $\displaystyle=$ $\displaystyle\mu_{i}\;\ell
r^{i}(y,z),$ $\displaystyle r^{i-1}f(y,z)$ $\displaystyle=$
$\displaystyle\rho_{i}\;\ell r^{i}(y,z).$

  2. (b)

For every $z\in D^{i}_{i-1}(x,y)$ we have

$\displaystyle r^{i}\ell(y,z)$ $\displaystyle=$
$\displaystyle\kappa_{i}\;r^{i-1}(y,z)+\mu_{i}\;\ell r^{i}(y,z),$
$\displaystyle r^{i-1}f(y,z)$ $\displaystyle=$
$\displaystyle\theta_{i}\;r^{i-1}(y,z)+\rho_{i}\;\ell r^{i}(y,z).$

Moreover, $\rho_{i}=0$ if the set $D^{i}_{i+1}(x,y)$ is nonempty for some
$y\in\Gamma(x)$.

###### Proof.

Pick an integer $i\;(1\leq i\leq d)$ and recall that by Lemma 5.1 equations
(5.0.1) and (5.0.2) hold. Pick $y\in\Gamma(x)$.

${(a)}$ Pick $z\in D^{i}_{i+1}(x,y)\cup D^{i}_{i}(x,y)$ and observe that by
Lemma 3.3 the $(z,y)$-entry of the left-hand side of (5.0.1) ((5.0.2),
respectively) equals $r^{i}\ell(y,z)$ ($r^{i-1}f(y,z)$, respectively). On the
other hand, again by Lemma 3.3, the $(z,y)$-entry of
$E_{i}^{*}R^{i-1}E_{1}^{*}$ ($E_{i}^{*}R^{i}LE_{1}^{*}$, respectively) equals
$0$ ($\ell r^{i}(y,z)$, respectively). Therefore, the $(z,y)$-entry of the
right-hand side of (5.0.1) ((5.0.2), respectively) equals $\mu_{i}\;\ell
r^{i}(y,z)$ ($\rho_{i}\;\ell r^{i}(y,z)$, respectively).

${(b)}$ Pick now $z\in D^{i}_{i-1}(x,y)$ and observe that by Lemma 3.3 the
$(z,y)$-entry of the left-hand side of (5.0.1) ((5.0.2), respectively) equals
$r^{i}\ell(y,z)$ ($r^{i-1}f(y,z)$, respectively). On the other hand, again by
Lemma 3.3, the $(z,y)$-entry of $E_{i}^{*}R^{i-1}E_{1}^{*}$
($E_{i}^{*}R^{i}LE_{1}^{*}$, respectively) equals $r^{i-1}(y,z)$ ($\ell
r^{i}(y,z)$, respectively). Therefore, the $(z,y)$-entry of the right-hand
side of (5.0.1) ((5.0.2), respectively) equals
$\kappa_{i}\;r^{i-1}(y,z)+\mu_{i}\;\ell r^{i}(y,z)$
($\theta_{i}\;r^{i-1}(y,z)+\rho_{i}\;\ell r^{i}(y,z)$, respectively).

Moreover, for $z\in D^{i}_{i+1}(x,y)$ we observe there is no $yz$-walk of the
shape $r^{i-1}f$ and so $\rho_{i}=0$ if the set $D^{i}_{i+1}(x,y)$ is nonempty
for some $y\in\Gamma(x)$ as $\ell r^{i}(y,z)>0$. The result follows. ∎

##  6 The distance partition

Throughout this section let $\Gamma=(X,{\cal R})$ denote a connected graph.
Let $x\in X$ and let $T=T(x)$. Suppose that the unique irreducible $T$-module
with endpoint $0$ is thin. Assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, which is thin. In this
section we have some comments about the combinatorial structure of the
intersection diagrams of $\Gamma$ with respect to the edge $\\{x,y\\}$, for
every $y\in\Gamma(x)$. In particular, we will discuss which of the sets
$D^{i}_{j}(x,y)$ are (non)empty.

######  Lemma 6.1.

With reference to Notation 3.4, the set $D^{i}_{i-1}(x,y)$ is nonempty for
every $i$ $\;(1\leq i\leq d)$ and for all $y\in\Gamma(x)$.

###### Proof.

Suppose there exist $i$ $\;(1\leq i\leq d)$ and $y\in\Gamma(x)$ such that the
set $D^{i}_{i-1}(x,y)$ is empty. Since $D^{1}_{0}(x,y)=\left\\{y\right\\}$ we
observe that $i\geq 2$. Moreover, we notice that
$D_{i+1}^{i}(x,y)\neq\emptyset$ or $D_{i}^{i}(x,y)\neq\emptyset$, as
otherwise, the set $\Gamma_{i}(x)=D^{i}_{i+1}(x,y)\cup D^{i}_{i}(x,y)\cup
D^{i}_{i-1}(x,y)$ is empty, contradicting that the eccentricity of $x$ equals
$d$. Let $k$ be the greatest integer such that
$D^{k}_{k-1}(x,y)\neq\emptyset$. Note that $1\leq k\leq i-1$. Since the set
$D_{i+1}^{i}(x,y)\cup D_{i}^{i}(x,y)\neq\emptyset$ then it is easy to see that
there exists an $xw$-path for $w\in D_{i+1}^{i}(x,y)\cup D_{i}^{i}(x,y)$,
passing through a vertex $z\in D_{k+1}^{k}(x,y)\cup D_{k}^{k}(x,y)$. So, the
numbers $r^{k+1}\ell(z)>0$ and $r^{k}(z)>0$. Moreover, for $u\in
D^{k}_{k-1}(x,y)$ we observe $r^{k+1}\ell(u)=0$ and $r^{k}(u)>0$. As the
trivial module is thin, this contradicts [8, Theorem 6]. The result follows. ∎

The proofs of the next results are ommited as it can be carried out using
similar ideas as the proofs of [5, Lemma 7.1], [5, Proposition 7.2] and [5,
Proposition 7.3], respectively.

######  Lemma 6.2.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. Pick an integer $i$ $\;(1\leq i\leq d)$ and assume for some
$y\in\Gamma(x)$, the set $D^{i}_{i+1}(x,y)\neq\emptyset$. Then the set
$D^{j}_{j}(x,y)$ is empty for every $j$ $\;(1\leq j\leq i)$ and for all
$y\in\Gamma(x)$.

The above lemma together with the fact that the set $D^{0}_{1}(x,y)$ is
nonempty for every $y\in\Gamma(x)$ motivate the next result.

######  Proposition 6.3.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. Pick $y\in\Gamma(x)$ and let $D^{i}_{j}=D^{i}_{j}(x,y)$. Then there
exists an integer $t:=t(y)\;(0\leq t\leq d)$ such that the following
${(i),(ii)}$ hold:

  1. (i)

For every $i\;(0\leq i\leq t)$ the set $D^{i}_{i+1}$ is nonempty and the set
$D^{i}_{i}(x,z)$ is empty for every $z\in\Gamma(x)$.

  2. (ii)

For every $i\;(t<i\leq d)$ the set $D^{i}_{i+1}$ is empty.

Moreover, $\Gamma_{i}(x)=D^{i}_{i+1}\cup D^{i}_{i-1}$ for every $0\leq i\leq
t$.

######  Proposition 6.4.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. Pick $y\in\Gamma(x)$. Let the sets $D^{i}_{j}=D^{i}_{j}(x,y)$ and let
$t(y)$ be as in Proposition 6.3. If there exists $j\;(1\leq j\leq d)$ such
that $D^{j}_{j}$ is nonempty then $D^{i}_{i}$ is nonempty for every
$t(y)<i\leq j$.

Propositions 6.3 and 6.4 help us to understand the combinatorial structure of
graphs which have, up to isomorphism, exactly one irreducible $T$-module with
endpoint $1$, which is thin.

We now consider the possible intersection diagrams of $\Gamma$ with respect to
the edge $\\{x,y\\}$, for every $y\in\Gamma(x)$. Let $d$ denote the
eccentricity of $x$. Then, for every $y\in\Gamma(x)$, we observe
$\epsilon(y)\in\\{d-1,d,d+1\\}$. Fix now $y\in\Gamma(x)$ arbitrarily. We have
two cases.

With reference to Proposition 6.3, it is easy to see the following
$(i)$-$(ii)$ are equivalent:

  1. (i)

The integer $t:=t(y)$ is independent of the choice of $y\in\Gamma(x)$.

  2. (ii)

For each $i\;(1\leq i\leq d)$, if for some $y\in\Gamma(x)$ the set
$D^{i}_{i+1}(x,y)\neq\emptyset$ then for every $y\in\Gamma(x)$ the set
$D^{i}_{i+1}(x,y)\neq\emptyset$ .

At this point, the next question naturally arises.

######  Question 6.5.

With reference to Notation 3.4 and Proposition 6.3, assume that $\Gamma$ has,
up to isomorphism, exactly one irreducible $T$-module with endpoint $1$, and
that this module is thin. Does the integer $t:=t(y)$ depend on the choice of
$y\in\Gamma(x)$?

The following results partially answer the above question. However, a proof of
the general case seems to need a nontrivial approach.

######  Proposition 6.6.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. For $y\in\Gamma(x)$, let $t(y)$ be as in Proposition 6.3. If for some
$z\in\Gamma(x)$ the set $D^{1}_{1}(x,z)$ is nonempty then the integer
$t:=t(y)$ does not depend on the choice of $y\in\Gamma(x)$.

###### Proof.

Suppose for some $z\in\Gamma(x)$ the set $D^{1}_{1}(x,z)$ is nonempty. Then,
by Lemma 6.2, the set $D^{1}_{2}(x,y)$ is empty for every $y\in\Gamma(x)$.
This shows that $t(y)=0$ for every $y\in\Gamma(x)$. The result follows. ∎

######  Proposition 6.7.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. For $y\in\Gamma(x)$, let $t(y)$ be as in Proposition 6.3. If for every
$y\in\Gamma(x)$ there exists an integer $i\;(1\leq i\leq d)$ such that the set
$D^{i}_{i}(x,y)$ is nonempty then the integer $t:=t(y)$ does not depend on the
choice of $y\in\Gamma(x)$.

###### Proof.

Pick $w\in\Gamma(x)$ such that $t(w)=\min\\{t(y)\mid y\in\Gamma(x)\\}$. Then,
by the choice of $w\in\Gamma(x)$, we have that $t(w)\leq t(y)$ for all
$y\in\Gamma(x)$. Let $k$ be the least integer such that
$D^{k}_{k}(x,w)\neq\emptyset$. We assert that $t(w)=k-1$. To prove our claim,
we first observe that, by Lemma 6.2, we have $D^{k}_{k+1}(x,w)=\emptyset$.
This shows that $t(w)\leq k-1$. Suppose now that $t(w)<k-1$. Then, $t(w)+1<k$
and, by the choice of $k$, $D^{t(w)+1}_{t(w)+1}(x,w)=\emptyset$, contradicting
Proposition 6.4. Therefore, we have that $t(w)=k-1$. Moreover, by Lemma 6.2,
the set $D^{k}_{k+1}(x,y)=\emptyset$ for all $y\in\Gamma(x)$. This yields that
$t(y)\leq t(w)$ for all $y\in\Gamma(x)$. Consequently, $t(y)=t(w)$ for all
$y\in\Gamma(x)$. The result follows. ∎

######  Proposition 6.8.

With reference to Notation 3.4, assume that $\Gamma$ has, up to isomorphism,
exactly one irreducible $T$-module with endpoint $1$, and that this module is
thin. For $y\in\Gamma(x)$, let $t(y)$ be as in Proposition 6.3. If $\Gamma$ is
a tree then the integer $t:=t(y)$ does not depend on the choice of
$y\in\Gamma(x)$.

###### Proof.

Pick $y\in\Gamma(x)$. Suppose there exists an integer $i\;(1\leq i\leq d)$
such that the set $D^{i}_{i+1}(x,y)$ is empty. Let $k$ be the least integer
such that $D^{k}_{k+1}(x,y)$ is empty. Since $\Gamma$ is bipartite and $x$ has
valency at least $2$, we observe $D^{1}_{2}(x,y)$ is not empty. This implies
that $k\geq 2$. By the choice of $k$, we have that the set $D^{k-1}_{k}(x,y)$
is nonempty. Then, since $\Gamma$ has no cycles, for a vertex $z\in
D^{k-1}_{k}(x,y)$ we have $b_{k-1}(x,z)=0$. By Lemma 6.1, the set
$D^{j}_{j-1}(x,y)$ is nonempty for every $j\;(1\leq j\leq d)$ and so, for
$w\in D^{k-1}_{k-2}(x,y)$, the scalar $b_{k-1}(x,w)>0$. This shows that
$\Gamma$ is not distance-regular around $x$. Therefore, by [8, Corollary 12]
the trivial module $T\widehat{x}$ is not thin, a contradiction. Hence, for
every integer $i\;(1\leq i\leq d)$ the set $D^{i}_{i+1}(x,y)$ is not empty.
This yields $t(y)=d$. The result follows. ∎

##  7 Examples

In this section we present some examples of graphs for which the equivalent
conditions of Theorem 3.5 hold for a certain vertex $x$. Several examples of
such graphs where $x$ is distance-regularized, are presented in [5, 7]. We
therefore turn our attention to the case when $x$ is not necessarily distance-
regularized. Recall that we are still refering to Definition 3.2 and Notation
3.4 throughout this section.

######  Example 7.1.

Let $\Gamma$ be the connected graph with vertex set
$X=\left\\{1,2,3,4,5,6\right\\}$ and edge set
$\mathcal{R}=\left\\{\left\\{1,2\right\\},\left\\{1,3\right\\},\left\\{2,3\right\\},\left\\{2,4\right\\},\left\\{2,5\right\\},\left\\{3,5\right\\},\left\\{3,6\right\\}\right\\}$.
See also Figure 1 and observe that $\Gamma$ is not bipartite. Fix vertex $1\in
X$ and note that $\epsilon(1)=2$. Notice that $\Gamma$ is not distance-regular
around $1$. Consider the Terwilliger algebra of $\Gamma$ with respect to
vertex $1$. It is now easy to verify that for every integer $i$ $\;(0\leq
i\leq 2)$ there exist scalars $\alpha_{i},\beta_{i}$, such that for every
$y\in\Gamma_{i}(x)$ the following hold:

$r^{i+1}\ell(y)=\alpha_{i}\;r^{i}(y),\qquad r^{i}f(y)=\beta_{i}\;r^{i}(y),$

with the values of $\alpha_{i},\beta_{i}\;(0\leq i\leq 2)$ as presented in
Table 1.

$i$ | 0 | 1 | 2
---|---|---|---
$\alpha_{i}$ | 2 | 3 | 0
$\beta_{i}$ | 0 | 1 | 0
Table 1: Values of scalars $\alpha_{i}$ and $\beta_{i}$, $(0\leq i\leq 2)$.

Therefore, by [8, Theorem 6] the trivial $T$-module is thin. Moreover,
properties ${(a),(b)}$ described in part ${(ii)}$ of Theorem 3.5 are satisfied
with the values of $\kappa_{i},\mu_{i},\theta_{i},\rho_{i}\;(1\leq i\leq 2)$
as presented in Table 2. Consequently, by Theorem 3.5, it holds that $\Gamma$
has, up to isomorphism, a unique irreducible $T$-module with endpoint $1$, and
this module is thin. Moreover, since $\dim(E^{*}_{1}V)=|\Gamma(x)|=2$, it is
easy to see that there is actually only one irreducible $T$-module with
endpoint $1$. This $T$-module has dimension $s=2$ and is spanned by
$w=\widehat{3}-\widehat{2}$ and $Rw=\widehat{6}-\widehat{4}$. Note also that
the partitions given by the intersection diagrams of $\Gamma$ with respect to
the edges $\\{1,2\\}$ and $\\{1,3\\}$ are not equitable.

|  $i$ 1 2 $\kappa_{i}$ 1 0 $\mu_{i}$ 1 0 $\theta_{i}$ -1 0 $\rho_{i}$ 1 0
---
| $4$$5$$6$$1$$2$$3$
---
Table 2:  Values of scalars $\kappa_{i}$, $\mu_{i}$, $\theta_{i}$ and $\rho_{i}$, $(1\leq i\leq 2)$. |  Figure 1:  Graph $\Gamma$ from Example 7.1.

We next give another example of a non-bipartite graph where the equivalent
conditions of Theorem 3.5 hold for a non-distance-regularized vertex $x$.

###  7.1 A construction

Our next goal is to focus on the construction of infinitely many new graphs,
that satisfy the equivalent conditions of Theorem 3.5 for a certain vertex. To
do this, we will need the folowing notation.

######  Notation 7.2.

Let $\Gamma$ and $\Sigma$ denote finite, simple graphs with vertex set $X$ and
$Y$, respectively. Assume that $\Gamma$ is a connected graph which is pseudo-
distance-regular around a vertex $x\in X$. Assume also that $\Sigma$ is
regular with order at least $2$. Consider the Cartesian product
$\Gamma\square\Sigma$. Namely, the graph with vertex set $X\times Y$ where two
vertices $(x,y)$ and $(x^{\prime},y^{\prime})$ are adjacent if and only if
$x=x^{\prime}$ and $y$ is adjacent to $y^{\prime}$, or $y=y^{\prime}$ and $x$
is adjacent to $x^{\prime}$. Let $H=H(\Gamma,\Sigma)$ denote the graph
obtained by adding a new vertex $w$ to the graph $\Gamma\square\Sigma$, and
connecting this new vertex $w$ with all vertices $(x,y)$, where $y$ is an
arbitrary vertex of $\Sigma$; see for example Figures LABEL:stable0002 and
LABEL:complete0002.

With reference to Notation 7.2, we observe that for an arbitrary vertex
$(x^{\prime},y^{\prime})$ of $H$ different from $w$, the distance between $w$
and $(x^{\prime},y^{\prime})$ satisfies
$\partial_{H}(w,(x^{\prime},y^{\prime}))=\partial_{\Gamma}(x,x^{\prime})+1.$
It thus follows that $d_{H}=d+1$, where $d_{H}$ is the eccentricity of $w$ in
$H$ and $d$ is the eccentricity of $x$ in $\Gamma$. Moreover, for $1\leq i\leq
d_{H}$ we have

$H_{i}(w)=\Gamma_{i-1}(x)\times Y=\\{(u,y)\mid u\in\Gamma_{i-1}(x),y\in Y\\}.$

In addition, it is easy to see that $H$ is distance-regular around $w$ if and
only if $\Gamma$ is distance-regular around $x$.

We are now ready to give some constructions of infinitely many graphs, that
satisfy the equivalent conditions of Theorem 3.5 for a certain vertex.

######  Proposition 7.3.

With reference to Notation 7.2, pick vertex $w$ in $H$ and consider the
Terwilliger algebra $T=T(w)$. Then, the trivial $T$-module is thin.

###### Proof.

Immediate from [8, Section 6.5]. ∎

With reference to Notation 7.2, in what follows, we use subscripts to
distinguish the number of walks of a particular shape in $H$ and in $\Gamma$.
For example, for $x^{\prime}\in\Gamma_{i}(x)$, we denote the number of walks
from $x$ to $x^{\prime}$ of the shape $r^{i+1}\ell$ with respect to $x$ by
$r^{i+1}\ell_{\Gamma}(x^{\prime})$. For $(x^{\prime},y^{\prime})\in H_{i}(w)$,
we denote the number of walks from $w$ to $(x^{\prime},y^{\prime})$ of the
shape $r^{i+1}\ell$ with respect to $w$ by
$r^{i+1}\ell_{H}((x^{\prime},y^{\prime}))$. We next study the instances when
$\Sigma$ is either an empty or a complete graph.

######  Proposition 7.4.

With reference to Notation 7.2, pick vertex $w$ in $H$ and consider the
Terwilliger algebra $T=T(w)$. If $\Sigma$ is isomorphic to the empty graph
$S_{n}\;(n\geq 2)$ then graph $H$ has, up to isomorphism, exactly one
irreducible $T$-module with endpoint $1$, which is thin.

###### Proof.

By Proposition 7.3, we first observe the trivial module is thin. We will next
show that $H$ satisfies the combinatorial conditions of Theorem 3.5. Suppose
that $\Sigma$ is isomorphic to the empty graph $S_{n}\;(n\geq 2)$. Pick
$(x,y)\in H(w)$ and consider the sets $D^{i}_{j}=D^{i}_{j}(w,(x,y))$. Since
the eccentricity of $x$ equals $d$ it is easy to see the sets
$D^{j}_{j+1}\;(0\leq j\leq d_{H})$ and $D_{j-1}^{j}\;(1\leq j\leq d_{H})$ are
all nonempty for all $(x,y)\in H(w)$. Consequently, by Lemma 6.2, the set
$D^{j}_{j}$ is empty for every $j\;(1\leq j\leq d_{H})$ and for all $(x,y)\in
H(w)$. In addition, we also notice

$\displaystyle D^{j}_{j+1}(w,(x,y))$ $\displaystyle=$
$\displaystyle\Gamma_{j-1}(x)\times(Y\setminus\\{y\\})$ $\displaystyle=$
$\displaystyle\\{(u,y^{\prime})\mid u\in\Gamma_{j-1}(x),y^{\prime}\in
Y,y^{\prime}\neq y\\},$ $\displaystyle D^{j}_{j-1}(w,(x,y))$ $\displaystyle=$
$\displaystyle\Gamma_{j-1}(x)\times\\{y\\}$ $\displaystyle=$
$\displaystyle\\{(u,y)\mid u\in\Gamma_{j-1}(x)\\}.$

Pick $(x^{\prime},y^{\prime})\in H_{i}(w)$ for $1\leq i\leq d_{H}$. We observe
that

$\displaystyle\ell
r^{i}_{H}\left((x,y),(x^{\prime},y^{\prime})\right)=r^{i-1}_{\Gamma}(x^{\prime})$
(7.1.1)

which is a positive integer since $\partial_{\Gamma}(x,x^{\prime})=i-1$
implies $r^{i-1}_{\Gamma}(x^{\prime})>0$. Moreover, for
$(x^{\prime},y^{\prime})\in D^{i}_{i+1}\;(1\leq i\leq d_{H})$ we have

$\displaystyle
r^{i}\ell_{H}\left((x,y),(x^{\prime},y^{\prime})\right)=r^{i-1}f_{H}\left((x,y),(x^{\prime},y^{\prime})\right)=0.$
(7.1.2)

Similarly, for $(x^{\prime},y^{\prime})\in D^{i}_{i-1}\;(1\leq i\leq d_{H})$
we have

$\displaystyle r^{i}\ell_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i}\ell_{\Gamma}(x^{\prime}),$ (7.1.3)
$\displaystyle r^{i-1}f_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i-1}f_{\Gamma}(x^{\prime}),$ (7.1.4)
$\displaystyle r^{i-1}_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i-1}_{\Gamma}(x^{\prime}).$ (7.1.5)

Since vertex $x$ is pseudo-distance-regularized, by [8, Theorem 6], we know
that for every integer $i$ $\;(0\leq i\leq d)$ there exist scalars
$\alpha_{i},\beta_{i}$, such that for every $z\in\Gamma_{i}(x)$ the following
hold:

$r^{i+1}\ell_{\Gamma}(z)=\alpha_{i}\;r^{i}_{\Gamma}(z),\qquad
r^{i}f_{\Gamma}(z)=\beta_{i}\;r^{i}_{\Gamma}(z).$ (7.1.6)

It follows from (7.1.3), (7.1.4), (7.1.5) and (7.1.6) that for $1\leq i\leq
d_{H}$ and for every $(x^{\prime},y^{\prime})\in D^{i}_{i-1}$ we have

$\displaystyle r^{i}\ell_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i}\ell_{\Gamma}(x^{\prime})$ (7.1.7)
$\displaystyle=$ $\displaystyle\alpha_{i-1}r^{i-1}_{\Gamma}(x^{\prime})$
$\displaystyle=$
$\displaystyle\alpha_{i-1}r^{i-1}_{H}\left((x,y),(x^{\prime},y^{\prime})\right),$
$\displaystyle r^{i-1}f_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i-1}f_{\Gamma}(x^{\prime})$ (7.1.8)
$\displaystyle=$ $\displaystyle\beta_{i-1}r^{i-1}_{\Gamma}(x^{\prime})$
$\displaystyle=$
$\displaystyle\beta_{i-1}r^{i-1}_{H}\left((x,y),(x^{\prime},y^{\prime})\right).$

Therefore, from (7.1.1), (7.1.2), (7.1.7) and (7.1.8), we see that vertex $w$
of $H$ satisfies the combinatorial conditions of Theorem 3.5 with the values
of $\kappa_{i}=\alpha_{i-1},\mu_{i}=0,\theta_{i}=\beta_{i-1},\rho_{i}=0$ for
every integer $i\;(1\leq i\leq d_{H})$. Consequently, $H$ has, up to
isomorphism, a unique irreducible $T$-module with endpoint $1$, and this
module is thin. ∎

######  Example 7.5.

Let $\Gamma$ be the connected graph presented in Example 7.1 and let $S_{n}$
denote the empty graph of $n$ vertices, for some integer $n\geq 2$. Let
$H=H(\Gamma,S_{n})$; see for example Figure LABEL:stable0002 for the case
$n=2$. Consider the Terwilliger algebra $T=T(w)$ of $H$ with respect to $w$.
Notice that $H$ is not distance-regular around $w$ since $\Gamma$ is not
distance-regular around $x$. However, the trivial module is thin by
Proposition 7.3. It follows from Table 1 and the above comments that the
properties ${(a),(b)}$ described in part ${(ii)}$ of Theorem 3.5 hold with the
values of $\kappa_{i},\mu_{i},\theta_{i},\rho_{i}\;(1\leq i\leq 3)$ as
presented in Table 3. Consequently, by Theorem 3.5, it holds that $H$ has, up
to isomorphism, a unique irreducible $T$-module with endpoint $1$, and this
module is thin. Moreover, since $\dim(E^{*}_{1}V)=|H(w)|=n$, it is easy to see
that there are actually $n-1$ irreducible $T$-modules with endpoint $1$ and
these isomorphic $T$-modules have dimension $s=3$.

$i$ 1 2 3 $\kappa_{i}$ 2 3 0 $\mu_{i}$ 0 0 0 $\theta_{i}$ 0 1 0 $\rho_{i}$ 0 0 0 Table 3:  Values of scalars $\kappa_{i}$, $\mu_{i}$, $\theta_{i}$ and $\rho_{i}$, $(1\leq i\leq 3)$. |
---|---

######  Proposition 7.6.

With reference to Notation 7.2, pick vertex $w$ in $H$ and consider the
Terwilliger algebra $T=T(w)$. If $\Sigma$ is isomorphic to the complete graph
$K_{n}\;(n\geq 2)$ then graph $H$ has, up to isomorphism, exactly one
irreducible $T$-module with endpoint $1$, which is thin.

###### Proof.

By Proposition 7.3, we first observe the trivial module is thin. We will next
show that $H$ satisfies the combinatorial conditions of Theorem 3.5. Suppose
that $\Sigma$ is isomorphic to the complete graph $K_{n}\;(n\geq 2)$. Pick
$(x,y)\in H(w)$ and consider the sets $D^{i}_{j}=D^{i}_{j}(w,(x,y))$. Since
the eccentricity of $x$ equals $d$ it is easy to see the sets
$D^{j}_{j}\;(1\leq j\leq d_{H})$ and $D_{j-1}^{j}\;(1\leq j\leq d_{H})$ are
all nonempty for all $(x,y)\in H(w)$. Consequently, by Lemma 6.2 the set
$D^{j}_{j+1}$ is empty for every $j\;(1\leq j\leq d_{H})$ and for all
$(x,y)\in H(w)$. In addition, we also notice

$\displaystyle D^{j}_{j}(w,(x,y))$ $\displaystyle=$
$\displaystyle\Gamma_{j-1}(x)\times(Y\setminus\\{y\\})$ (7.1.9)
$\displaystyle=$ $\displaystyle\\{(u,y^{\prime})\mid
u\in\Gamma_{j-1}(x),y^{\prime}\in Y,y^{\prime}\neq y\\},$ $\displaystyle
D^{j}_{j-1}(w,(x,y))$ $\displaystyle=$
$\displaystyle\Gamma_{j-1}(x)\times\\{y\\}$ (7.1.10) $\displaystyle=$
$\displaystyle\\{(u,y)\mid u\in\Gamma_{j-1}(x)\\}.$

Pick $(x^{\prime},y^{\prime})\in H_{i}(w)$ for $1\leq i\leq d_{H}$. We observe
that

$\displaystyle\ell
r^{i}_{H}\left((x,y),(x^{\prime},y^{\prime})\right)=r^{i-1}_{\Gamma}(x^{\prime})$
(7.1.11)

which is a positive integer since $\partial_{\Gamma}(x,x^{\prime})=i-1$
implies $r^{i-1}_{\Gamma}(x^{\prime})>0$. Moreover, since every vertex in
$D^{i}_{i}$ has no neighbours in $D^{i+1}_{i}$, for
$(x^{\prime},y^{\prime})\in D^{i}_{i}\;(1\leq i\leq d_{H})$, it follows that

$\displaystyle r^{i}\ell_{H}\left((x,y),(x^{\prime},y^{\prime})\right)=0.$
(7.1.12)

In addition, from the definition of $H$, (7.1.9) and (7.1.10), it is easy to
see every vertex $(x^{\prime},y^{\prime})\in D^{i}_{i}\;(1\leq i\leq d_{H})$
has exactly one neighbour in $D^{i}_{i-1}$ which is the vertex
$(x^{\prime},y)$. This implies the number of walks from $(x,y)$ to
$(x^{\prime},y^{\prime})$ of the shape $r^{i-1}f$ with respect to $w$ is equal
to the number of walks from $x$ to $x^{\prime}$ of the shape $r^{i-1}$ with
respect to $x$. Therefore, from the above comments and (7.1.11), for
$(x^{\prime},y^{\prime})\in D^{i}_{i}\;(1\leq i\leq d_{H})$,

$\displaystyle
r^{i-1}f_{H}\left((x,y),(x^{\prime},y^{\prime})\right)=r^{i-1}_{\Gamma}(x^{\prime})=\ell
r^{i}_{H}\left((x,y),(x^{\prime},y^{\prime})\right).$ (7.1.13)

Similarly, for $(x^{\prime},y^{\prime})\in D^{i}_{i-1}\;(1\leq i\leq d_{H})$
we have

$\displaystyle r^{i}\ell_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i}\ell_{\Gamma}(x^{\prime}),$ (7.1.14)
$\displaystyle r^{i-1}f_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i-1}f_{\Gamma}(x^{\prime}),$ (7.1.15)
$\displaystyle r^{i-1}_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i-1}_{\Gamma}(x^{\prime}).$ (7.1.16)

Since vertex $x$ is pseudo-distance-regularized, by [8, Theorem 6], we know
that for every integer $i$ $\;(0\leq i\leq d)$ there exist scalars
$\alpha_{i},\beta_{i}$, such that for every $z\in\Gamma_{i}(x)$ the following
hold:

$r^{i+1}\ell_{\Gamma}(z)=\alpha_{i}\;r^{i}_{\Gamma}(z),\qquad
r^{i}f_{\Gamma}(z)=\beta_{i}\;r^{i}_{\Gamma}(z).$ (7.1.17)

It follows from (7.1.14), (7.1.15), (7.1.16) and (7.1.17) that for $1\leq
i\leq d_{H}$ and for every $(x^{\prime},y^{\prime})\in D^{i}_{i-1}$ we have

$\displaystyle r^{i}\ell_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i}\ell_{\Gamma}(x^{\prime})$ (7.1.18)
$\displaystyle=$ $\displaystyle\alpha_{i-1}r^{i-1}_{\Gamma}(x^{\prime})$
$\displaystyle=$
$\displaystyle\alpha_{i-1}r^{i-1}_{H}\left((x,y),(x^{\prime},y^{\prime})\right),$
$\displaystyle r^{i-1}f_{H}\left((x,y),(x^{\prime},y^{\prime})\right)$
$\displaystyle=$ $\displaystyle r^{i-1}f_{\Gamma}(x^{\prime})$ (7.1.19)
$\displaystyle=$ $\displaystyle\beta_{i-1}r^{i-1}_{\Gamma}(x^{\prime})$
$\displaystyle=$
$\displaystyle\beta_{i-1}r^{i-1}_{H}\left((x,y),(x^{\prime},y^{\prime})\right).$

Therefore, from (7.1.11), (7.1.12), (7.1.13), (7.1.18) and (7.1.19), we see
that vertex $w$ of $H$ satisfies the combinatorial conditions of Theorem 3.5
with the values of
$\kappa_{i}=\alpha_{i-1},\mu_{i}=0,\theta_{i}=\beta_{i-1}-1,\rho_{i}=1$ for
every integer $i\;(1\leq i\leq d_{H})$. Consequently, $H$ has, up to
isomorphism, a unique irreducible $T$-module with endpoint $1$, and this
module is thin. ∎

######  Example 7.7.

Let $\Gamma$ be the connected graph presented in Example 7.1 and let $K_{n}$
denote the complete graph of $n$ vertices, for some integer $n\geq 2$. Let
$H=H(\Gamma,K_{n})$; see for example Figure LABEL:complete0002 for the case
$n=2$. Consider the Terwilliger algebra $T=T(w)$ of $H$ with respect to $w$.
Notice that $H$ is not distance-regular around $w$ since $\Gamma$ is not
distance-regular around $x$. However, the trivial module is thin by
Proposition 7.3. It follows from Table 1 and the above comments that the
properties ${(a),(b)}$ described in part ${(ii)}$ of Theorem 3.5 hold with the
values of $\kappa_{i},\mu_{i},\theta_{i},\rho_{i}\;(1\leq i\leq 3)$ as
presented in Table 4. Consequently, by Theorem 3.5, it holds that $H$ has, up
to isomorphism, a unique irreducible $T$-module with endpoint $1$, and this
module is thin. Moreover, since $\dim(E^{*}_{1}V)=|H(w)|=n$, it is easy to see
that there are actually $n-1$ irreducible $T$-modules with endpoint $1$ and
these isomorphic $T$-modules have dimension $s=3$.

$i$ 1 2 3 $\kappa_{i}$ 2 3 0 $\mu_{i}$ 0 0 0 $\theta_{i}$ -1 0 -1 $\rho_{i}$ 1 1 1 Table 4:  Values of scalars $\kappa_{i}$, $\mu_{i}$, $\theta_{i}$ and $\rho_{i}$, $(1\leq i\leq 3)$. |
---|---

We are now ready to prove the main result of this subsection.

######  Theorem 7.8.

With reference to Notation 7.2, pick vertex $w$ in $H$ and consider the
Terwilliger algebra $T=T(w)$. Graph $H$ has, up to isomorphism, exactly one
irreducible $T$-module with endpoint $1$, which is thin if and only if
$\Sigma$ is either isomorphic to the empty graph $S_{n}\;(n\geq 2)$ or to the
complete graph $K_{n}\;(n\geq 2)$.

###### Proof.

By Proposition 7.3, we observe the trivial module is thin. Assume first that
$H$ has, up to isomorphism, exactly one irreducible $T$-module with endpoint
$1$, which is thin. We next claim that $\Sigma$ is either isomorphic to the
empty graph $S_{n}\;(n\geq 2)$ or to the complete graph $K_{n}\;(n\geq 2)$.
Let $Y$ denote the vertex set of $\Sigma$. If $|Y|=2$ then the statement
trivially follows. So, to prove this assertion, assume that $|Y|>2$. Given any
three vertices $y,y^{\prime},y^{\prime\prime}\in Y$, suppose there exist both
a pair of adjacent vertices and a pair of nonadjacent vertices in $\Sigma$.
Without loss of generality we could assume that $y$ is adjacent to
$y^{\prime}$ but not to $y^{\prime\prime}$. Since $y$ and $y^{\prime}$ are
adjacent, we thus have that $(x,y^{\prime})$ is a common neighbour of both $w$
and $(x,y)$ in $H$. Moreover, note that
$\partial_{H}(w,(x,y^{\prime\prime}))=1$ and since $y$ and $y^{\prime\prime}$
are not adjacent, $\partial_{H}((x,y),(x,y^{\prime\prime}))=2$. Hence, the
sets $D^{1}_{2}(w,(x,y))$ and $D^{1}_{1}(w,(x,y))$ are both nonempty,
contradicting Lemma 6.2. Consequently, any three vertices in $Y$ either form a
stable set or a clique. This clearly implies that $\Sigma$ is either
isomorphic to the empty graph $S_{n}\;(n\geq 2)$ or to the complete graph
$K_{n}\;(n\geq 2)$, which proves our claim. Notice also that the second part
of the result immediately follows from Proposition 7.4 and Proposition 7.6.
This finishes the proof. ∎

##  8 Acknowledgement

The author would like to thank Štefko Miklavič for helpful and constructive
comments that greatly contributed to improving the final version of this
article. This work is supported in part by the Slovenian Research Agency
(research program P1-0285, research project J1-2451 and Young Researchers
Grant).

##  9 Data availability

Data sharing is not applicable to this article as no datasets were generated
or analysed during the current study.

## References

  * [1] J. M. P. Balmaceda and A. C. L. Reyes, Terwilliger algebras of certain group association schemes, Journal of the Math. Soc. Philippines, 44 (2021), 19-28.
  * [2] B.V. Collins, The Terwilliger algebra of an almost-bipartite distance-regular graph and its antipodal $2$-cover, Discrete Math., 216(1-3) (2000), 35-69.
  * [3] B. Curtin, Bipartite distance-regular graphs, Part I, Graphs Comb., 15(2) (1999), 143-158.
  * [4] B. Curtin and K. Nomura, 1-homogeneous, pseudo-1-homogeneous, and 1-thin distance-regular graphs, J. Comb. Theory. Ser. B, 93 (2005), 279-302.
  * [5] B. Fernández, Certain graphs with exactly one irreducible $T$-module with endpoint 1, which is thin, J. Algebraic Combin., (2022), 1-21.
  * [6] B. Fernández and Š. Miklavič, On the Terwilliger algebra of distance-biregular graphs, Linear Algebra Appl. 597 (2020), 18-32.
  * [7] B. Fernández and Š. Miklavič, On bipartite graphs with exactly one irreducible $T$-module with endpoint $1$, which is thin, Eur. J. Comb., 97 (2021), 103387.
  * [8] B. Fernández and Š. Miklavič, On the trivial $T$-module of a graph. Electron. J. Comb, 29 (2) (2022), P2.48.
  * [9] M. A. Fiol, On pseudo-distance-regularity, Linear Algebra Appl. 323 (2001), 145-165.
  * [10] M. A. Fiol and E. Garriga, On the algebraic theory of pseudo-distance-regularity around a set, Linear Algebra Appl. 298 (1999), 115-141.
  * [11] Godsil, C. D. and Shawe-Taylor, J., Distance-regularised graphs are distance-regular or distance-biregular, J. Comb. Theory. Ser. B 43(1) (1987), 14-24.
  * [12] A. Hanaki, Modular Terwilliger algebras of association schemes., Graphs Comb. 37.5 (2021), 1521-1529.
  * [13] L. Hou, B. Hou, N. Kang and S. Gao, The Terwilliger algebra of the halved $n$-cube from the viewpoint of its automorphism group action, Eur. J. Comb., 101 (2022), 103480.
  * [14] S. D. Li, Y. Z. Fan, T. Ito, M. Karimi, and J. Xu, The isomorphism problem of trees from the viewpoint of Terwilliger algebras, J. Combin. Theory. Ser. A 177 (2021).
  * [15] X. Liang, T. Ito and Y. Watanabe, The Terwilliger algebra of the Grassmann scheme $J_{q}(N,D)$ revisited from the viewpoint of the quantum affine algebra $U_{q}\left(\mathfrak{\widehat{sl}}_{2}\right)$, Linear Algebra Appl., 596 (2020), 117-144.
  * [16] M. S. MacLean and Š. Miklavič, On bipartite distance-regular graphs with exactly one non-thin $T$-module with endpoint two, Eur. J. Comb. 64 (2017), 125-137.
  * [17] M. S. MacLean, and Š. Miklavič, On bipartite distance-regular graphs with exactly two irreducible $T$-modules with endpoint two, Linear Algebra Appl. 515 (2017), 275-297.
  * [18] M. S. MacLean, and Š. Miklavič, On a certain class of $1$-thin distance-regular graphs, Ars Math. Contemp. 18.2 (2020), 187-210.
  * [19] M. S. MacLean, Š. Miklavič and S. Penjić, On the Terwilliger algebra of bipartite distance-regular graphs with $\Delta_{2}=0$ and $c_{2}=1$, Linear Algebra Appl. 496 (2016), 307-330.
  * [20] M. S. MacLean, Š. Miklavič and S. Penjić, An $A$-invariant subspace for bipartite distance-regular graphs with exactly two irreducible $T$-modules with endpoint $2$, both thin, J. Algebraic Combin. 48 (2018), 511-548.
  * [21] M. S. MacLean and S. Penjić, A combinatorial basis for Terwilliger algebra modules of a bipartite distance-regular graph., Discrete Mathematics 344.7 (2021), 112393.
  * [22] Š. Miklavič and S. Penjić, On the Terwilliger algebra of certain family of bipartite distance-regular graphs with $\Delta_{2}=0$. The Art of Discrete and Applied Mathematics. 3.2 (2020), P2-04.
  * [23] S. Penjić, On the Terwilliger algebra of bipartite distance-regular graphs with $\Delta_{2}=0$ and $c_{2}=2$, Discrete Math. 340 (2017), 452-466.
  * [24] H. Tanaka and T. Wang, The Terwilliger algebra of the twisted Grassmann graph: the thin case, Electron. J. Comb. 27 (4) (2020), P4.15.
  * [25] P. Terwilliger, Algebraic Graph Theory.
Available at `https://icu-hsuzuki.github.io/lecturenote/`

  * [26] P. Terwilliger, The subconstituent algebra of an association scheme, (part I), J. Algebraic Combin. 1 (1992), 363-388.
  * [27] P. Terwilliger and A. Žitnik, The quantum adjacency algebra and subconstituent algebra of a graph, J. Combin. Theory Ser. A 166 (2019), 297-314.
  * [28] J. Xu, T. Ito, and S. Li, Irreducible Representations of the Terwilliger Algebra of a Tree, Graphs Combin. 37.5 (2021), 1749-1773.