# Pattern polynomial graphs

A. Satyanarayana Reddy111Department of Mathematics and Statistics, Indian
Institute of Technology, Kanpur, India 208016; (e-mail: satya@iitk.ac.in).
Shashank K Mehta 222Department of Computer Science and Engineering, Indian
Institute of Technology, Kanpur, India 208016; (e-mail:
skmehta@cse.iitk.ac.in). This work was partly supported by Research-I
Foundation, IIT-Kanpur.

###### Abstract

A graph $X$ is said to be a pattern polynomial graph if its adjacency algebra
is a coherent algebra. In this study we will find a necessary and sufficient
condition for a graph to be a pattern polynomial graph. Some of the properties
of the graphs which are polynomials in the pattern polynomial graph have been
studied. We also identify known graph classes which are pattern polynomial
graphs.

Keywords: Adjacency algebra of a graph, coherent algebra, automorphisms of a
graph, distance regular graphs.
Mathematics Subject Classification(2010): 05C50, 05E40,05E18

##  1 Introduction and preliminaries

Let $M_{n}({\mathbb{C}})$ denote the set of all $n\times n$ matrices over the
field of complex numbers ${\mathbb{C}}$. Let ${\mathbb{C}}[A]$ denote the set
of all matrices which are polynomials in $A$ with coefficients from
${\mathbb{C}}$. Clearly ${\mathbb{C}}[A]$ is an algebra over ${\mathbb{C}}$
for any $A\in M_{n}({\mathbb{C}})$. The dimension of ${\mathbb{C}}[A]$ over
${\mathbb{C}}$ as a vector space, is the degree of the minimal polynomial of
$A$. If $A$ is diagonalizable, then from the following lemma, it’s dimension
is equal to the number of distinct eigenvalues of $A$.

######  Lemma 1.1 (Hoffman $\&$ Kunze [10]).

A matrix is diagonalizable if and only if its minimal polynomial has all
distinct linear factors over ${\mathbb{C}}$.

######  Definition 1.1.

Hadamard product of two $n\times n$ matrices $A$ and $B$ is denoted by $A\odot
B$ and is defined as $(A\odot B)_{xy}=A_{xy}B_{xy}$.

Two $n\times n$ matrices $A$ and $B$ are said to be disjoint if their Hadamard
product is the zero matrix.

######  Definition 1.2.

A subalgebra of $M_{n}(\mathbb{C})$ is called coherent if it contains the
matrices $I$ and $J$ and if it is closed under conjugate-transposition and
Hadamard multiplication. Here $J$ denotes the matrix with every entry being
$1$.

######  Theorem 1.2.

[4] Every coherent algebra contains unique basis of mutually disjoint $0,1$\-
matrices (matrices with entries either $0$ or $1$).

We call this unique basis of mutually disjoint 0-1 matrices as a _standard
basis_.

######  Corollary 1.3.

Every $0,1$-matrix in a coherent algebra is the sum of one or more matrices in
its standard basis.

###### Proof.

Let $\mathcal{M}$ be a coherent algebra over ${\mathbb{C}}$ with its standard
basis $\\{M_{1},\ldots M_{t}\\}$. Let $B\in\mathcal{M}$ be a $0,1$-matrix,
then $B=\sum_{i=1}^{t}a_{i}M_{i}$ where $a_{i}\in{\mathbb{C}}$. $B=B\odot
B=\sum_{i=1}^{t}a_{i}^{2}M_{i}\Rightarrow a_{i}^{2}=a_{i}$. Hence the result
follows. ∎

######  Corollary 1.4.

If $\mathcal{M}$ is a commutative coherent algebra over ${\mathbb{C}}$, then
$\dim(\mathcal{M})\leq n$.

###### Proof.

Since $J$ commutes with every element in $\mathcal{M}$. Hence all the
row(column) sums of every matrix in $\mathcal{M}$ are equal. Consequently the
number of elements in the standard basis of $\mathcal{M}$ is atmost $n$, as
the matrices in the standard basis of $\mathcal{M}$ are disjoint and whose sum
is $J$. ∎

######  Observation 1.5.

The intersection of coherent algebras is again a coherent algebra.

######  Definition 1.3.

Let $A\in M_{n}({\mathbb{C}})$, then coherent closure of $A$, denoted by
$\langle\langle A\rangle\rangle$ or ${\mathcal{CC}}(A)$, is the smallest
coherent algebra containing $A$.

In Section 2 we will see a necessary and sufficient condition for any matrix
$A\in M_{n}({\mathbb{C}})$ such that ${\mathbb{C}}[A]={\mathcal{CC}}(A)$. In
the remaining sections we consider $A$ to be the adjacency matrix of a graph
$X$. If $A$ is the adjacency matrix of a graph $X$ and
${\mathbb{C}}[A]={\mathcal{CC}}(A)$, then $X$ will be called a pattern
polynomial graph. Some of the properties of pattern polynomial graphs are
given in Section 3. In Section 4 we will see a few graph classes which are
pattern polynomial graphs. Few partially balanced incomplete block designs
from pattern polynomial graphs are constructed in Section 5. Properties of
graphs which are polynomials in the pattern polynomial graph are provided in
the Section 6.

##  2 ${\mathbb{C}}[A]={\mathcal{CC}}(A)$

In this section we will see a necessary and sufficient condition for a matrix
$A\in M_{n}({\mathbb{C}})$ such that ${\mathbb{C}}[A]={\mathcal{CC}}(A)$. For
that we construct a vector space which lies in between
${\mathbb{C}}[A]\;and\;{\mathcal{CC}}(A)$ as follows.

Let $\ell$ be the degree of the minimal polynomial of $A$. Then
$\\{I,A,\ldots,A^{\ell-1}\\}$ is a basis for ${\mathbb{C}}[A]$ over
${\mathbb{C}}$. Let
$\textbf{y}=(y_{0},y_{1}\ldots,y_{\ell-1})\in{\mathbb{C}}^{\ell}$ be a
variable and

$B(\textbf{y})=y_{0}I+y_{1}A+\dots
y_{l-1}A^{\ell-1}=\begin{bmatrix}p_{11}(\textbf{y})&p_{12}(\textbf{y})&\dots&p_{1n}(\textbf{y})\\\
p_{21}(\textbf{y})&p_{22}(\textbf{y})&\dots&p_{2n}(\textbf{y})\\\
\vdots&\vdots&\ddots&\vdots\\\
p_{n1}(\textbf{y})&p_{n2}(\textbf{y})&\dots&p_{nn}(\textbf{y})\end{bmatrix}.$

Where $p_{ij}(\textbf{y})=p_{ij}(y_{0},y_{1}\ldots,y_{\ell-1})$ is a
polynomial in the variables $y_{0},y_{1},\ldots,y_{\ell-1}$. Let us assume
$\\{q_{1}(\textbf{y}),q_{2}(\textbf{y}),\ldots,q_{r}(\textbf{y})\\}$ be the
set of distinct polynomials in the matrix $B(\textbf{y})$. We define the
matrices called pattern matrices of $A$, as $P_{j}\;(1\leq j\leq r)$ as

$(P_{j})_{s,t}=\begin{cases}1,&{\mbox{ if
}}B(\textbf{y})_{s,t}=q_{j}(\textbf{y}),\\\ 0,&{\mbox{otherwise.
}}\end{cases}$

Let ${\mathcal{L}}(A)=L\\{P_{1},P_{2},\ldots,P_{r}\\}$ denote the linear span
of matrices $P_{1},\ldots,P_{r}$. Then ${\mathcal{L}}(A)$ is a subspace of
$M_{n}({\mathbb{C}})$. From the definition of ${\mathcal{L}}(A)$ we have the
following observation.

######  Observation 2.1.

  1. 1.

$P_{i}\odot P_{j}=0\;\forall i,j\;1\leq i,j\leq r$,
$\sum_{i=1}^{r}P_{i}=J\in{\mathcal{L}}(X)$, $I\in{\mathcal{L}}(A)$.

  2. 2.

${\mathcal{L}}(A)$ is closed under Hadamard product.

###### Proof.

Let $M,N\in{\mathcal{L}}(A)$, so
$M=\sum_{i=1}^{r}a_{i}P_{i}\;,N=\sum_{i=1}^{r}b_{i}P_{i}$ where
$a_{i},b_{i}\in{\mathbb{C}}$. Then $M\odot
N=\sum_{i=1}^{r}a_{i}b_{i}P_{i}\in{\mathcal{L}}(A)$. ∎

  3. 3.

${\mathcal{L}}(A)$ is the smallest subspace of $M_{n}({\mathbb{C}})$ closed
under Hadamard product and contains all powers of $A$. Consequently
${\mathbb{C}}[A]\subseteq{\mathcal{L}}(A)\subseteq{\mathcal{CC}}(A)$ and
$l\leq r$.

  4. 4.

If $P_{i}^{T}\in\\{P_{1},P_{2},\ldots,P_{r}\\}\;for\;all\;1\leq i\leq r$, then
${\mathcal{L}}(A)$ is also closed under conjugate transposition. In
particular, if $A$ is symmetric, then all pattern matrices are symmetric hence
${\mathcal{L}}(A)$ is closed under conjugate transposition.

With the above observation, we are providing the main result of this section.

######  Theorem 2.2.

Let $A\in M_{n}({\mathbb{C}})$ be a symmetric matrix. Then
${\mathbb{C}}[A]={\mathcal{CC}}(A)$ if and only if $\ell=r$.

###### Proof.

If ${\mathbb{C}}[A]={\mathcal{CC}}(A)$, then
${\mathbb{C}}[A]={\mathcal{L}}(A)$ hence $\ell=r$. Conversely suppose $\ell=r$
then ${\mathbb{C}}[A]={\mathcal{L}}(A)$. In particular ${\mathcal{L}}(A)$ is
closed under ordinary multiplication. Hence from the above obseravtion
${\mathcal{L}}(A)$ is a coherent algebra but ${\mathcal{CC}}(A)$ is the
smallest coherent algebra containing ${\mathbb{C}}[A]$. Hence the result
follows. ∎

##  3 Pattern polynomial graphs

From now onwards we suppose that $A$ (or A(X)) is the adjacency matrix of a
graph $X$, hence $A$ is a symmetric $0,1$ matrix. We denote ${\mathbb{C}}[A]$
by ${\mathcal{A}}(X)$, ${\mathcal{CC}}(A)$ by ${\mathcal{CC}}(X)$ and
${\mathcal{L}}(A)$ by ${\mathcal{L}}(X)$. We call ${\mathcal{A}}(X)$ as the
adjacency algebra of the graph $X$, ${\mathcal{CC}}(X)$ as coherent closure of
$X$. First we will provide a few results on adjacency algebra of a graph. Then
we will see some additional properties of the vector space ${\mathcal{L}}(X)$.
For two vertices $u$ and $v$ of a connected graph $X$, let $d(u,v)$ denote the
length of the shortest path from $u$ to $v$. Then the diameter of a connected
graph $X=(V,E)$ is $\max\\{d(u,v):\;u,v\in V\\}$. It is shown in Biggs [3]
that if $X$ is a connected graph with diameter $d$, then

$d+1\leq\dim({\mathcal{A}}(X))\leq n$ (1)

where $\dim({\mathcal{A}}(X))$ is the dimension of ${\mathcal{A}}(X)$ as a
vector space over ${\mathbb{C}}$.

A graph $X_{1}=(V(X_{1}),E(X_{1}))$ is said to be isomorphic to the graph
$X_{2}=(V(X_{2}),E(X_{2}))$, written $X_{1}\cong X_{2}$, if there is a one-to-
one correspondence $\rho:V(X_{1})\rightarrow V(X_{2})$ such that
$\\{v_{1},v_{2}\\}\in E(X_{1})$ if and only if
$\\{\rho(v_{1}),\rho(v_{2})\\}\in E(X_{2})$. In such a case, $\rho$ is called
an isomorphism of $X_{1}$ and $X_{2}$. An isomorphism of a graph $X$ onto
itself is called an automorphism. The collection of all automorphisms of a
graph $X$ is denoted by $\text{Aut}(X)$. It is well known that $\text{Aut}(X)$
is a group under composition of two maps. It is easy to see that
$\text{Aut}(X)=\text{Aut}(X^{c})$, where $X^{c}$ is the complement of the
graph X. If $X$ is a graph with $n$ vertices we can think of $\text{Aut}(X)$
as a subgroup of ${\mathcal{S}}_{n}$. Under this correspondence, if a graph
$X$ has $n$ vertices then $\text{Aut}(X)$ consists of $n\times n$ permutation
matrices and for each $g\in\text{Aut}(X)$, $P(g)$ will denote the
corresponding permutation matrix. The next result gives a method to check
whether a given permutation matrix is an element of $\text{Aut}(X)$ or not.

######  Lemma 3.1 (Biggs [3]).

Let A be the adjacency matrix of a graph $X$. Then $g\in\text{Aut}(X)$ is an
automorphism of $X$ if and only if $P(g)A=AP(g)$.

The following result is very useful in this work, which provides the necessary
and sufficient condition for a graph to be connected and regular.

######  Lemma 3.2 (Biggs [3]).

A graph $X$ is connected regular if and only if $J\in{\mathcal{A}}(X)$.

######  Corollary 3.3.

If $X$ is a regular graph then $J$ is polynomial in either $A$ or $A^{c}$.

###### Proof.

For every graph $X$, either $X$ or $X^{c}$ is connected. Hence the result
follow from the above Lemma. ∎

Let $X$ be a connected regular graph. Then from the above lemma we have
$A(X^{c})\in{\mathcal{A}}(X)$. Hence we have the following corollary.

######  Corollary 3.4.

Let $X$ be a connected regular graph. Then $X^{c}$ is connected if and only if
${\mathcal{A}}(X)={\mathcal{A}}(X^{c})$.

######  Definition 3.1.

A graph $X$ is said to be a _pattern polynomial graph_ if its pattern matrices
are polynomials in the adjacency matrix of $X$.

######  Lemma 3.5.

A graph $X$ is a pattern polynomial graph if and only if
${\mathcal{A}}(X)={\mathcal{CC}}(X)$.

Consequently if $X$ is a pattern polynomial graph, then
${\mathcal{A}}(X)={\mathcal{L}}(X)={\mathcal{CC}}(X)$. For any graph $X$, we
have ${\mathcal{L}}(X)={\mathcal{L}}(X^{c})$ and
${\mathcal{CC}}(X)={\mathcal{CC}}(X^{c})$. Hence we have the following result.

######  Corollary 3.6.

Let $X$ be a pattern polynomial graph and $X^{c}$ is also connected. Then
${\mathcal{A}}(X)={\mathcal{L}}(X)={\mathcal{CC}}(X)={\mathcal{A}}(X^{c})={\mathcal{L}}(X^{c})={\mathcal{CC}}(X^{c})$.

###  3.1 Properties of pattern polynomial graphs

In this subsection we prove that if $X$ is a pattern polynomial graph, then
$X$ is necessarily a
a) connected regular graph b) distance polynomial graph c) walk regular graph
d) strongly distance-balanced graph. e) edge regular graph whenever $A$ is
also a pattern matrix. We also show that every pattern polynomial graph except
$K_{2}$ (complete graph with 2 vertices) has at least one multiple eigenvalue.
In particular, if $X$ is a pattern polynomial graph with odd number of
vertices, then we show that $\dim({\mathcal{A}}(X))\leq\frac{n-1}{2}$.
Throughout this section we suppose that $X$ is a pattern polynomial graph that
is ${\mathcal{A}}(X)={\mathcal{L}}(X)={\mathcal{CC}}(X)$ or $\ell=r$. From
Lemma 3.2 we have the following result.

######  Lemma 3.7.

Every pattern polynomial graph is a connected regular graph.

It is easy to see that the converse of the above lemma is not true. The above
lemma provides a necessary condition to have
${\mathcal{A}}(X)={\mathcal{L}}(X)$. That is if the graph $X$ is either not
connected or not regular, then ${\mathcal{A}}(X)\subsetneq{\mathcal{L}}(X)$.
Now we will state another necessary condition stronger than this.

Distance polynomial graph

Let $X=(V,E)$ be a connected graph with diameter $d$. The _$k$ -th distance
matrix_ $A_{k}(0\leq k\leq d)$ of $X$, is defined as
$(A_{k})_{rs}=\left\\{\begin{array}[]{cl}1,&{\mbox{ if }}d(v_{r},v_{s})=k\\\
0,&{\mbox{ otherwise.}}\end{array}\right.$
It follows that

$A_{0}=I\;\mbox{(Identity matrix)},\;A_{1}=A,\;A_{0}+A_{1}+\dots+A_{d}=J.$

A connected graph $X$ of diameter $d$ is said to be a distance polynomial
graph if $A_{k}\in{\mathcal{A}}(X)\;for\;0\leq k\leq d$. From the Lemma 3.2,
the following observation is evident.

######  Observation 3.8.

Every distance polynomial graph is a regular connected graph. The converse is
generally not true but every regular connected graph of diameter $2$ is
distance polynomial.

######  Lemma 3.9.

If $X$ be a connected graph of diameter $d$, then
$A_{k}\in{\mathcal{L}}(X)\;(0\leq k\leq d)$, where $A_{k}$ is the $k$-th
distance matrix of $X$.

###### Proof.

We prove the result by induction on $d$.
$A_{0}(=I),A_{1}(=A)\in{\mathcal{A}}(X)\subseteq{\mathcal{L}}(X)$. So the
result is true for $d=1$. Suppose that
$A_{0},A_{1},\ldots,A_{s-1}\in{\mathcal{L}}(X)$. Then $J-I-A_{0}-A_{1}-\dots-
A_{s-1}\in{\mathcal{L}}(X)$. Let $M=A^{s}\odot(J-I-A_{1}-\dots-
A_{s-1})\in{\mathcal{L}}(X)$. Observe that $M_{ij}\neq 0$ if and only if
$(A_{s})_{ij}=1$. As $M\in{\mathcal{L}}(X)$ we have

$M=\sum_{i=1}^{r}a_{i}P_{i}\;\mbox{where}\;a_{i}\in{\mathbb{C}}.$ (2)

Hence $A_{s}=\sum_{i:a_{i}\neq 0}P_{i}\in{\mathcal{L}}(X)$. ∎

Now from Corollary 1.3, every distance matrix is the sum of one or more
pattern matrices.

######  Corollary 3.10.

Every pattern polynomial graph is a distance polynomial graph.

From Observation 3.8, every connected regular graph of diameter $2$ is
distance polynomial. But all connected regular graphs of diameter $2$ are not
pattern polynomial graphs.

######  Definition 3.2 (Paul M.Weichsel [15]).

Let $v$ be a vertex in the graph $X$ of diameter $d$. The generalized degree
of $v$ is the $d$-tuple $(k_{1},k_{2}\ldots,k_{d})$, where $k_{i}$ is the
number of vertices whose distance from $v$ is $i$. The graph G is called
_super-regular_ if each vertex has the same generalized degree.

######  Theorem 3.11 (Paul M.Weichsel [15]).

Let $X$ be a connected graph of diameter $d$. $X$ is super-regular graph if
and only if $(A_{i}A_{j})_{rs}=(A_{j}A_{i})_{rs}$ for all $r,s$.

From the Corollary 3.10 every pattern polynomial graph is a super regular
graph. In the present literature super-regular graphs are also called
distance-degree regular or strongly distance-balanced graphs for details refer
[14].

Walk-regular graph
A graph $X$ is said to be walk-regular if for each $s$, the number of closed
walks of length $s$ starting at a vertex $v$ is independent of the choice of
$v$.

######  Theorem 3.12.

[9] Let $A$ be the adjacency matrix of a graph $X$. Then $X$ is walk-regular
if and only if the diagonal entries of $A^{s}\;\forall s$ are all equal.

The following lemma and corollary can be obtained from the Corollary 1.4 and
above theorem.

######  Lemma 3.13.

Every pattern polynomial graph is a walk-regular graph.

######  Corollary 3.14.

If $X$ is pattern polynomial graph then every pattern matrix other than the
identity matrix is the adjacency matrix of a regular graph.

######  Remark 3.15.

Let $X$ be a pattern polynomial graph and $P\in{\mathcal{A}}(X)$ be a
permutation matrix. Then from Corollary 1.3 and from the above result $P$ is
an element in the standard basis of ${\mathcal{A}}(X)$. Further it is easy to
see that the set of all permutation matrices in ${\mathcal{A}}(X)$ forms an
elementary abelian 2-group since matrices in ${\mathcal{A}}(X)$ are symmetric.

Let $X$ be a pattern polynomial graph and $\\{I=P_{1},P_{2},\ldots,P_{r}\\}$
be the set of its pattern matrices. Let us call the graph $X_{P_{i}}\;2\leq
i\leq r$ as pattern graph of $X$ with adjacency matrix $P_{i}$. Then form
Lemma 3.1, we have $\text{Aut}(X)\subseteq\text{Aut}(X_{P_{i}})$. In fact in
the next section we will show that
$\text{Aut}(X)\subseteq\text{Aut}(X_{P_{i}})$ is true even if $X$ is not a
pattern polynomial graph. Now we will show that every pattern polynomial graph
except $K_{2}$ has at least one multiple eigenvalue. In order to prove this,
we need the following definition and the result.

######  Definition 3.3.

A graph is said to be vertex transitive if its automorphism group acts
transitively on $V$. That is for any two vertices $x,y\in V,\exists g\in G$
such that $g(x)=y$.

######  Lemma 3.16.

[Biggs [3]] Let $X$ be a $k$-regular vertex transitive graph, and $\lambda$ be
a simple eigenvalue of $X$. Then

$\lambda=\left\\{\begin{array}[]{cl}k,&{\mbox{ if }}\;|V|\;\mbox{is odd},\\\
\mbox{one of the integers}\;2\alpha-k\;(\;0\leq\alpha\leq k),&{\mbox{
if}}\;|V|\;\mbox{is even.}\end{array}\right.$

######  Corollary 3.17.

If $X$ is a vertex transitive graph and $X\neq K_{2}$, then $X$ has at least
one multiple eigenvalue.

######  Corollary 3.18.

If $X$ is a pattern polynomial graph and $X\neq K_{2}$, then $X$ has a
multiple eigenvalue.

###### Proof.

If all eigenvalues of $X$ are simple, then $\dim({\mathcal{A}}(X))=n$ so every
pattern matrix is a symmetric permutation matrix whose sum is $J$.
Consequently $X$ is a vertex transitive graph. ∎

We can extend the above result to arbitrary graphs in the following manner.

######  Corollary 3.19.

Let $X$ be a graph with $n>2$ vertices and ${\mathcal{CC}}(X)$ is a
commutative algebra. Then $\dim({\mathcal{A}}(X))\leq n-1$ and
$\dim({\mathcal{CC}}(X))\leq n$.

###### Proof.

First observe that $X$ has at least one multiple eigenvalue if and only if
$\dim({\mathcal{A}}(X))\leq n-1$. Now from the Corollary 1.4, we have
$\dim({\mathcal{CC}}(X))\leq n$. If $\dim({\mathcal{A}}(X))=n$, then we will
get a contradiction from above corollary. ∎

If $X$ is a pattern polynomial graph with odd number of vertices, then from
Corollary 3.14 we have stronger result than above.

######  Lemma 3.20.

If $X$ is a pattern polynomial graph with odd number of vertices, then
$\dim({\mathcal{A}}(X))\leq\frac{n+1}{2}$.

###### Proof.

First observe that $\dim({\mathcal{A}}(X))$ is the number of pattern matrices.
From Corollary 3.14, all pattern graphs of $X$ are regular with odd number of
vertices. Consequently each is an even regular graph with regularity $\geq 2$.
Hence $X$ has atmost $\frac{n-1}{2}$ pattern graphs. ∎

A graph is said to be an edge-regular graph if any two of its adjacent
vertices have the same number of common neighbours. The following result is
easy to see.

######  Lemma 3.21.

If $X$ is a pattern polynomial graph and its adjacency matrix itself is a
pattern matrix then $X$ is an edge-regular graph.

###### Proof.

Let $X$ be a pattern polynomial graph with adjacency matrix $A$. Let
$\\{P_{0}=I,P_{1}=A,P_{2},\ldots,P_{r}\\}$ be the standard basis of
${\mathcal{A}}(X)$. Hence $A^{2}=a_{0}I+a_{1}A+a_{2}P_{2}+\dots+a_{r}P_{r}$
where $a_{i}\in{\mathbb{C}}$. Consequently any two adjacent vertices have
exactly $a_{1}$ common neighbours. ∎

In the following section, we see few classes of graphs which satisfy the
condition $\ell=r$. Consequently they are pattern polynomial graphs

##  4 Some graph classes which are pattern polynomial

In this section we will prove that the following classes of graphs are pattern
polynomial graphs a)orbit polynomial graphs b) distance regular graphs hence
distance transitive graphs c) connected compact regular graphs.

######  Definition 4.1.

Let $G$ be a subset of $n\times n$ permutation matrices forming a group. Then
${\mathcal{V}}_{{\mathbb{C}}}(G)=\\{A\in M_{n}({\mathbb{C}}):PA=AP\;\forall
P\in G\\}$ forms an algebra over ${\mathbb{C}}$ called the centralizer algebra
of the group $G$.

######  Definition 4.2.

If G is a group acting on a set $V$, then $G$ also acts on $V\times V$ by
$g(x,y)=(g(x),g(y))$. The orbits of G on $V\times V$ are called orbitals. In
the context of graphs, the orbitals of graph $X$ are orbitals of its
automorphism group $\text{Aut}(X)$ acting on the vertex set of $X$. That is,
the orbitals are the orbits of the arcs/non-arcs of the graph $X=(V,E)$. The
number of orbitals is called the rank of $X$.

An orbital can be represented by a $0,1$-matrix $M$ where $M_{ij}$ is $1$ if
$(i,j)$ belongs to the orbital. We can associate directed graphs to these
matrices. If the matrices are symmetric, then these can be treated as
undirected graphs.

######  Observation 4.1.

  * •

The ‘1’ entries of any orbital matrix are either all on the diagonal or all
are off diagonal.

  * •

The orbitals containing $1$’s on the diagonal will be called diagonal
orbitals.

######  Definition 4.3.

The centralizer algebra of a graph $X$ denoted by ${\mathcal{V}}(X)$ is the
centralizer algebra of its automorphism group acting on the vertex set of $X$.

######  Theorem 4.2.

[11] ${\mathcal{V}}_{(}X)$ is a coherent algebra and orbitals of
$\text{Aut}(X)$ acting on the vertex set of $X$ form its unique 0-1 matrix
basis.

Since $\text{Aut}(X)=\text{Aut}(X^{c})$, we have ${\mathcal{V}}(X)=V(X^{c})$.
Also ${\mathcal{CC}}(X)$ is the smallest coherent algebra containing $A(X)$
and ${\mathcal{V}}(X)$ is a coherent algebra of $X$ containing $A(X)$ so
${\mathcal{CC}}(X)\subseteq{\mathcal{V}}(X)$.

#### Orbit polynomial graphs

######  Definition 4.4.

A graph $X=(V,E)$ is orbit polynomial graph if each orbital matrix is a member
of ${\mathcal{A}}(X)$. That is, each orbital matrix is a polynomial in $A$.

######  Lemma 4.3.

If $X$ is orbit polynomial graph if and only if
${\mathcal{A}}(X)={\mathcal{V}}(X)$

If $X$ is a orbit polynomial graph, then
${\mathcal{A}}(X)={\mathcal{CC}}(X)={\mathcal{V}}(X)$. Hence every orbit
polynomial graph is a pattern polynomial graph.

If $X$ is an orbit polynomial graph and $X^{c}$ is connected, then from above
lemma we have
${\mathcal{A}}(X)={\mathcal{A}}(X^{c})={\mathcal{CC}}(X)=CC(X^{c})={\mathcal{V}}(X)=V(X^{c})$.
So we have the following result.

######  Corollary 4.4.

If $X$ is an orbit polynomial graph and $X^{c}$ is connected then $X^{c}$ is
also a orbit polynomial graph.

For any graph $X$, we have
${\mathcal{A}}(X)\subseteq{\mathcal{L}}(X)\subseteq{\mathcal{CC}}(X)\subseteq{\mathcal{V}}(X)$.
Consequently from Corollary 1.3 every pattern matrix is the sum of one or more
orbital matrices. Further by definition, orbital matrices commute with all
automorphisms of $X$ hence we have the following result.

######  Lemma 4.5.

Let $X$ be any graph and $\\{P_{1},P_{2},\ldots,P_{r}\\}$ be the set of all
pattern matrices of adjacency matrix of $X$. Then
$\text{Aut}(X)\subseteq\text{Aut}(X_{P_{i}})\;1\leq i\leq r$.

Every connected vertex transitive graph of prime order is an orbit polynomial
graph, see [Beezer [1]]. Following lemma gives a stronger result.

######  Lemma 4.6.

If $X$ is a connected graph of prime order, then $X$ is orbit polynomial graph
if and only if ${\mathcal{V}}(X)$ is commutative.

###### Proof.

If $X$ is an orbit polynomial graph then clearly ${\mathcal{V}}(X)$ is
commutative. Conversely suppose that ${\mathcal{V}}(X)$ is commutative, then
the identity matrix is in the standard basis of ${\mathcal{V}}(X)$.
Consequently $X$ is a vertex transitive graph, hence the result follows. ∎

An easy consequence of this lemma is that if $X$ is a connected graph of prime
order and ${\mathcal{V}}(X)$ is commutative, then $X$ is a pattern polynomial
graph.

#### Distance transitive graphs

######  Definition 4.5.

A graph $X$ is _distance transitive_ if for all vertices $u,v,x,y$ of $X$ such
that $d(u,v)=d(x,y)$ then there is a $g$ in $\text{Aut}(X)$ satisfying
$g(u)=x$ and $g(v)=y$.

######  Remark 4.7.

From the definition of distance transitivity following facts are immediate: a)
For a distance transitive graph with diameter $d$, distance matrices and
orbital matrices coincide, consequently its rank is $d+1$. b) From Equation 1
and the fact that ${\mathcal{A}}(X)\subseteq{\mathcal{V}}(X)$, if $X$ is a
distance transitive graph with diameter $d$, then dimension of
${\mathcal{A}}(X)$ is $d+1$. Further orbital matrices form a basis for
${\mathcal{A}}(X)$. This also implies the following lemma.

Now the following result is immediate from the Theorem 4.11 and the above
Remark.

######  Lemma 4.8.

Every distance transitive graph is an orbit polynomial graph.

Converse of the above lemma is not true, as every vertex transitive graph of
prime order is not a distance transitive graph. so we have
Distance transitive graph $\Rightarrow$ Orbit polynomial graph $\Rightarrow$
Pattern polynomial graph $\Rightarrow$ Distance polynomial graph.

#### Compact graphs

######  Definition 4.6.

A graph $X$ is said to be _compact_ if every doubly stochastic matrix which
commutes with $A(X)$ is a convex combination of matrices from $\text{Aut}(X)$.

A permutation group on a set X is generously transitive if, given any two
points, there is a permutation which interchanges them.

######  Theorem 4.9.

[8] Let $X$be a connected regular graph with $r$ distinct eigenvalues. If
$X$is compact, then $\text{Aut}(X)$ is a generously transitive permutation
group with rank $r$.

In a compact connected regular graph $X$ the number of distinct eigenvalues of
$A(X)$ is same as the number of orbitals. It is also the dimension of
${\mathcal{A}}(X)$. Hence we have the following corollary from the fact that
${\mathcal{A}}(X)\subseteq{\mathcal{V}}(X)$.

######  Corollary 4.10.

Every compact connected regular graph is orbit polynomial graph.

Godsil [8] showed that if $n\geq 7$, then the line graph of the complete graph
$K_{n}$, is a distance transitive graph but not compact graph. It is also easy
to check that if $X$ is compact, then so is its compliment $X^{c}$ . Hence if
$X$ is connected compact regular graph and $X^{c}$ is also connected, then
$X^{c}$ is compact connected regular graph but it need not be a distance
transitive graph $X=C_{6}$(the cycle graph) is such an example.

Now we will see class of graphs which are pattern polynomial graphs but need
not be orbit polynomials graphs.

#### Distance regular Graphs

######  Definition 4.7.

A connected graph is distance regular if for any two vertices $u$ and $v$, the
number of vertices at distance $i$ from $u$ and $j$ from $v$ depends only on
$i$, $j$, and the distance between $u$ and $v$. These graphs are necessarily
regular, since $u$ may be equal to $v$.

It is easy to see that every distance transitive graph is distance regular. In
fact, there are many distance regular graphs whose automorphism group is
trivial [13]. The following theorem establishes that every distance regular
graph is a pattern polynomial graph.

######  Theorem 4.11.

[Damerell [5]] Let $X$ be a distance regular graph with diameter $d$. Then
$\\{A_{0},A_{1},\dots,A_{d}\\}$ is a basis for the adjacency algebra
${\mathcal{A}}(X)$, and consequently the dimension of ${\mathcal{A}}(X)$ is
$d+1$.

######  Corollary 4.12.

Every distance regular graph is a pattern polynomial graph.

Observe that if $X$ is a distance regular graph then $A$ itself is a pattern
matrix. Consequently if $X$ is a distance regular graph with diameter $\geq
3$, then $X^{c}$ is not distance regular. Now if $X$ is a distance regular
graph and $X^{c}$ is connected then from Corollary 3.6
${\mathcal{A}}(X)={\mathcal{A}}(X^{c})={\mathcal{CC}}(X)={\mathcal{CC}}(X^{c})$.
Hence $X^{c}$ is also pattern polynomial graph but it need not be a distance
regular graph for example $C_{6}^{c}$. Further there are distance regular
graphs whose automorphism group is trivial [13]. So they can’t be orbit
polynomial graphs. Finally, if $X$ is a distance regular graph with diameter
$\geq 3$ with trivial automorphism group and $X^{c}$ is connected, then
$X^{c}$ is neither distance regular nor orbit polynomial graph, but it is a
pattern polynomial graph.

The following diagram gives the relationship among some of the graph classes
which we studied in this work.

Regular connected GraphsDistance polynomial graphsPattern polynomial
graphsOrbit polynomial graphsCompact connected regular graphsDistance
transitive graphsDistance regular graphs

##  5 PBIBD(t)s from pattern polynomial graphs

A design is an ordered pair $(V,\mathcal{B})$ with point set $V$ and set of
blocks $\mathcal{B}$ such that $\mathcal{B}$ is a collection of subsets of
$V$.

A design $(V,\mathcal{B})$ is called $t-(v,k,{\lambda})$ design(some times
only t-design) if $|V|=v,|B|=k\;\forall B\in\mathcal{B}$ and each subset of
$V$ of cardinality $t$ is contained in ${\lambda}$ blocks. One can show by
counting that a $t$-design is an $i$-design for each $0\leq i\leq t$. In fact
a $t-(v,k,{\lambda})$ design is a $i-(v,k,{\lambda}_{i})$ design with
${\lambda}_{i}={\lambda}{v-i\choose i-1}/{k-i\choose t-i}$ for each $0\leq
i\leq t$.

A balanced incomplete block design(BIBD) is a 2-design. The parameters
${\lambda}_{1}$ and ${\lambda}_{0}$ are usually denoted by $r_{1}$
(replication number) and $b$ (number of blocks).

######  Definition 5.1.

Given $v$symbols $1,2,\ldots,v$, a relation satisfying the following condition
is said to be an _symmetric association scheme_ with $m$ association classes:

  1. 1.

Any two symbols $\alpha$ and $\beta$ are either first,second,.. or mth
associates and this relationship is symmetrical. We denote $(\alpha,\beta)=i$,
when $\alpha$ and $\beta$ ith associates.

  2. 2.

Every symbol $\alpha$ has $n_{i}$, $i$th associates, the number $n_{i}$ being
independent of $\alpha$.

  3. 3.

If $(\alpha,\beta)=i$ the number of symbols $\gamma$ that satisfy
simultaneously $(\alpha,\gamma)=j$ and $(\beta,\gamma)=j^{\prime}$ is
$p^{i}_{jj^{\prime}}$ and this number is independent of $\alpha$ and $\beta$.
Further $p^{i}_{jj^{\prime}}=p^{i}_{j^{\prime}j}$

The numbers $v,n_{i},p^{i}_{jj^{\prime}}$ are called the parameters of the
association scheme. If the relations are not symmetric, then it is called an
association scheme.

Let $R_{i}=\\{(\alpha,\beta)|(\alpha,\beta)=i\\}$ be the set of all $i$-th
associates. Then the relation $R_{i}$ of an association scheme can be
described by a $0,1$-matrices $A_{i}$. Hence above definition can be described
in terms of matrices as follows.

An association scheme with $d$ associate classes is a set
$\mathfrak{A}=\\{A_{0},\ldots,A_{d}\\}$ of 0,1-matrices such that

  1. 1.

$A_{0}=I$.

  2. 2.

$A_{0}+A_{1}+\dots+A_{d}=J$.

  3. 3.

$A_{i}^{T}\in\mathfrak{A}$.

  4. 4.

$A_{i}A_{j}=A_{j}A_{i}\in span(\mathfrak{A})$.

If $A_{i}^{T}=A_{i}(1\leq i\leq d)$, then $\mathfrak{A}$ is a symmetric
association scheme also called Bose-Mesner algebra. For example, if $X$ is a
pattern polynomial graph, then ${\mathcal{A}}(X)$ is a Bose-Mesner algebra.
But every Bose-Mesner algebra can not be obtained in this way. Now we will
give an example of a Bose-Mesner algebra $\mathfrak{A}$ which is not equal to
adjacency algebra of any graph.

Let $G$ be a finite abelian group of order $n(>2)$. Each element of $G$ gives
rise to a permutation of $G$, the permutation corresponding to ’$a$ maps g in
$G$ to $ga$’. Hence for each element $g$ in $G$ we have a permutation matrix
$P_{g}$; the map $g\rightarrow P_{g}$ is a group homomorphism. Therefore
$P_{g}P_{h}=P_{h}P_{g},P(g^{-1})=P_{g}^{T}$. We have $P(1)=I$ and $\sum_{g\in
G}P_{g}=J$. Hence the matrices $P_{g}$ forms an association scheme with $v-1$
classes. Note the association scheme obtained in this way is same as
centralizer algebra ${\mathcal{V}}_{\mathbb{C}}(G)$ which is further equal to
group algebra ${\mathbb{C}}[G]$. The restricted centralizer algebra
${\mathcal{V}}_{r}(G)$, consisting of all real, symmetric matrices in
${\mathcal{V}}_{\mathbb{C}}(G)$ is a real subalgebra of
${\mathcal{V}}_{\mathbb{C}}(G)$, which is closed under Hadamard product and
spanned by the matrices $P_{g}+P^{T}_{g}\;\forall g\in G$. That is
${\mathcal{V}}_{r}(G)$ is a symmetric association scheme. Further if we assume
that $G$ is an elementary abelian 2-group, then
${\mathbb{C}}[G]={\mathcal{V}}_{r}(G)={\mathcal{V}}_{\mathbb{C}}(G)$.
Consequently ${\mathbb{C}}[G]$ is a Bose-Mesner algebra and
$\dim({\mathbb{C}}[G])=n$. Now from Corollary 3.19 there exists no graph $X$
with $n>2$ vertices such that ${\mathcal{A}}(X)={\mathbb{C}}[G]$.

######  Definition 5.2.

Given an $m$-association scheme on $v$-symbols a PBIBD(m) with $m$ associate
classes is defined as follows. A PBIBD(m) with $m$ associate classes is an
arrangement of $v$ symbols in $b$ sets of size $k(<v)$ such that

  1. 1.

Every symbol occurs at most once in a set.

  2. 2.

Every symbol occurs in $r$ sets.

  3. 3.

Two symbols $\alpha$ and $\beta$ occur in $\lambda_{i}$ sets, if
$(\alpha,\beta)=i$ and $\lambda_{i}$ is independent of symbols $\alpha$ and
$\beta$.

The numbers $v,b,r,k,\lambda_{i}$ are the parameters of the PBIBD. The PBIBD
is usually identified by the association scheme of the symbols. For more
information on design theory the reader is referred to Raghavarao [12]. For
any PBIBD(t) we will write the parameters as
$(v,b,r_{1},k_{1},\lambda_{1},\ldots,\lambda_{t})$ where $v$ is the number of
points , $b$ is the number of blocks, $r_{1}$ is called the replication
number, $k_{1}$ is the number of elements in any block of the design.

If $N$ is the incidence matrix of a design $\mathcal{D}$, then we say that the
design $\mathcal{D}$ is obtained from the graph $X$ if
$NN^{T}\in{\mathcal{A}}(X)$. For example, if $X$ is a pattern polynomial graph
with $n$ vertices , then

  1. 1.

Every BIBD with $n$ points is obtained from $X$. In fact every t-design with
$n$ points and $t\geq 2$ is obtained from $X$.

  2. 2.

Let a graph $Y$ be a polynomial in $X$ and $\mathcal{D}_{1}=(V(Y),E(Y))$ be a
design with points as vertices of graph $Y$ and blocks as edges of $Y$. Then
$NN^{T}=D+A(Y)\in{\mathcal{A}}(X)$ where $N$ is the incidence matrix of design
$\mathcal{D}_{1}$, which is also 0,1-incidence matrix of the graph $Y$ and $D$
is the diagonal matrix with diagonal entries are degree of vertices of $Y$.
Note that $\mathcal{D}_{1}$ is a PBIBD(r), where $r$ is the degree of the
minimal polynomial of $X$.

Let $v$ be any vertex in a graph $Z$, $N(v)$ be the set of vertices which are
adjacent to $v$ in $Z$, $\mathcal{B}_{2}=\\{N(v)|v\in V(Z)\\}$ and
$\mathcal{B}_{3}=\\{N(v)\cup\\{v\\}|v\in V(Z)\\}$. If
$\mathcal{D}_{2}=(V(Z),\mathcal{B}_{2})$ and
$\mathcal{D}_{3}=(V(Z),\mathcal{B}_{3})$, then $\mathcal{D}_{2}$ and
$\mathcal{D}_{3}$ are designs on $V(Z)$ with
$n=|V(Z)|=|\mathcal{B}_{2}|=|\mathcal{B}_{3}|=b$. Hence $A(Z)$ is the
incidence matrix of the designs $\mathcal{D}_{2}$ and $I+A(Z)$ is the
incidence matrix of $\mathcal{D}_{3}$. If $Z$ is a $k$-regular graph, then all
blocks in the design $\mathcal{D}_{2}(\mathcal{D}_{3})$ are $k$-subsets ($k+1$
subsets) of $V(Z)$. And each vertex belongs exactly $k$ ($k+1$) blocks. In
other words $\mathcal{D}_{2}(\mathcal{D}_{3})$ is a 1-design with
$r_{1}=k_{1}$. Further if we assume $Z$ is a polynomial in a pattern
polynomial graph $X$, then the designs $\mathcal{D}_{2}$ and $\mathcal{D}_{3}$
are PBIBD(r)s where $r$ is the degree of minimal polynomial of $X$. Hence we
have the following result.

######  Lemma 5.1.

Let a k-regular graph $Y$ be a polynomial in a pattern polynomial graph $X$
with $n$ vertices and $\mathcal{D}_{i},i=2,3$ are designs on $V(Y)$ defined as
above. Then $\mathcal{D}_{2}(\mathcal{D}_{3})$ is a PBIBD(r) obtained from $X$
with parameters
$(n,n,k,k,\lambda_{1},\ldots,\lambda_{r})((n,n,k+1,k+1,\lambda^{{}^{\prime}}_{1},\ldots,\lambda^{{}^{\prime}}_{r}))$
for some ${\lambda}_{i}$ and ${\lambda}_{i}^{{}^{\prime}}$.

##  6 On the polynomial of a pattern polynomial graph

A graph $Y$ is said to be a polynomial in a graph $X$ if
$A(Y)\in{\mathcal{A}}(X)$. For an arbitrary graph $X$ it seems difficult to
find whether a given graph is polynomial in $X$ or not. This question is
answered for orbit poynomial graph and distance regular graphs by [Robert
A.Beezer [2]] and [Paul M.Weichsel [15]] respectively. In the following lemma
we generalize those results to all pattern polynomial graphs.

######  Lemma 6.1.

If $X$ is a pattern polynomial graph with standard basis
$\\{P_{1},P_{2},\ldots,P_{r}\\}$ where $P_{1}=I$, then a graph $Y$ is a
polynomial in $X$ if and only if $A(Y)=\sum_{i=2}^{r-1}a_{i}P_{i}$ where
$a_{i}\in\\{0,1\\}$.

###### Proof.

Direct consequence of Corollary 1.3. ∎

######  Corollary 6.2.

There are $2^{r-1}$ graphs in the adjacency algebra of a pattern polynomial
graph $X$, where $r$ is the degree of the minimal polynomial of $A(X)$.

Another trivial fact is as follows.

######  Lemma 6.3.

Let a graph $Y$ be a polynomial in a pattern polynomial graph $X$, then
${\mathcal{CC}}(Y)\subseteq{\mathcal{CC}}(X)$.

If a graph $Y$ is a polynomial in a pattern polynomial graph $X$, then
${\mathcal{CC}}(Y)$ is a symmetric (every matrix in ${\mathcal{CC}}(Y)$ is
symmetric) commutative algebra. Hence

  1. 1.

$Y$ is a walk regular graph,

  2. 2.

$Y$ is a strongly distance-balanced graph, from Lemma 3.9,

  3. 3.

$Y$ has a multiple eigenvalue, whenever $Y\neq K_{2}$, from Corollary 3.19,

  4. 4.

$\dim({\mathcal{CC}}(Y))\leq n-1$, from Corollary 3.19. Further if the number
of vertices in $Y$ is odd, then $\dim({\mathcal{CC}}(Y))\leq\frac{n+1}{2}$.

Now it is interesting to answer the following question: If $Y$ is a graph such
that ${\mathcal{CC}}(Y)$ is symmetric commutative algebra, then “does there
exist a pattern polynomial graph $X$ such that $Y$ is a polynomial in $X$?”.
For example, if $Y$ is a circulant graph (Cayley graph on cyclic group) with
$n$ vertices, then clearly ${\mathcal{CC}}(Y)$ is symmetric commutative
algebra and it is also known that $Y$ is a polynomial in cycle graph $C_{n}$,
which is a pattern polynomial graph.

If a graph $Y$ is a polynomial in a graph $X$, then there exists a unique
polynomial $p_{Y}(x)\in{\mathbb{C}}[x]$, with degree less than the degree of
the minimal of $X$, such that $A(Y)=p_{Y}(A(X))$. It is called representor
polynomial of $Y$. If $X$ is a pattern polynomial graph and
$A(Y)=\sum_{i}a_{i}P_{i}$, then $p_{Y}=\sum_{i}a_{i}p_{X_{P_{i}}}$. If a graph
$Y$ is a polynomial in $X$ with representor polynomial $p_{Y}(x)$, then the
eigenvalues of $A(Y)$ are $p_{Y}(\lambda_{i})$, where $\lambda_{i}\;(0\leq
i\leq n-1)$ are eigenvalues of $A(X)$.

The following result gives whether a graph $Y$ which is a polynomial in a
graph $X$ is singular or not. Recall a graph is said to be singular if its
adjacency matrix is singular.

######  Lemma 6.4.

Let a graph $Y$ be a polynomial in a graph $X$. Then $Y$ is singular if and
only if $\deg(\gcd(p(x),p_{Y}(x)))\geq 1$, where $p(x)$ is the minimal
polynomial of $A(X)$ and $p_{Y}(x)$ is the representor polynomial of $Y$ with
respect to $X$.

## References

  * [1] Robert A.Beezer, Orbit polynomial graphs of prime order, Discrete Mathematics 67 (1987) 139-147.
  * [2] Robert A.Beezer, A disrespectful polynomial, Linear Algebra and its Applications, Volume 128, January 1990, Pages 139-146.
  * [3] N.L. Biggs, Algebraic Graph Theory(second ed.), Cambridge University Press, Cambridge (1993).
  * [4] A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance regular Graphs, Springer-Verlag, (1989).
  * [5] Damerell. R.M, On Moore graphs, proc. Cambridge Philos. sec.74,227-236.
  * [6] Philip J. Davis. Circulant matrices ”A Wiley-interscience publications,(1979).
  * [7] Chris D. Godsil $\&$ Gordon Royle. Algebraic Graph Theory, Springer-Verlag, (2001).
  * [8] Chris D. Godsil, Compact graphs and equitable partitions , Linear algebra and applications, 255:259-266 (1997).
  * [9] C. D. Godsil and B. D. McKay, Feasibility conditions for the existence of walk-regular graphs, Linear algebra and its applications 30:51-61(1980).
  * [10] Kenneth Hoffman and Ray Kunge, Linear Algebra (second edition), Prentice-Hall, (1971).
  * [11] M.klin, C.R$\ddot{u}$cker,G.R$\ddot{u}$cker, G.Tinhofer, Algebraic Combinatorics in Mathematical Chemistry Methods and Algorithms.I. Permutation Groups and Coherent (cellular) Algebras. Technical report Technische universit$\ddot{a}$t M$\ddot{u}$nchen, TUM-M9510(1995).
  * [12] Raghavarao, Constructions and combinatorial problems in Design of Experiments, Wiley, New York (1971).
  * [13] E.Spence, Regular two-graphs on 36 vertices, Linear Alg. Appl. 226-228 (1995), 459-497.
  * [14] Sergio Cabello and Primo$\check{z}$ Luk$\check{s}$i$\check{c}$, The complexity of obtaining a distance-balanced graph, The electronic journal of combinatorics 18 (2011), P49.
  * [15] Paul M.Weichsel, On distance-regularity in graphs, Journal of combinatorial theory, Series B 32, 156-161 (1982).