# The Class ofq-Cliqued Graphs: Eigen-Bi-Balanced Characteristic, Designs, and an Entomological Experiment

Authors: Paul August Winter; Carol Lynne Jessop; Costas Zachariades
Journal: International Journal of Combinatorics
 (2015)

---

## Abstract

Much research has involved the consideration of graphs which have subgraphs of a particular kind, such as cliques.  Known classes of graphs which are eigen-bi-balanced, that is, they have a paira, b of  nonzero distinct eigenvalues, whose sum and product are integral, have been investigated.  In this paper we will define a new class of graphs, called q-cliqued graphs, on q
2
+
1 vertices, which contain q cliques each of order q connected to a central vertex, and then prove that these q-cliqued graphs are eigen-bi-balanced with respect to a conjugate pair whose sum is -
1 and product 1
-
q. These graphs can be regarded as design graphs, and we use a specific example in an entomological experiment.


---

## Body

## 1. Introduction

There is much interest in considering graphs which have subgraphs of a particular kind, such as cliques—see Bapat and Sivasubramanian [1], Graham et al. [2], and Liazi et al. [3]. Known classes of graphs which are eigen-bi-balanced are considered in Winter and Jessop [4]. These graphs have an associated pair of (real) conjugate eigenvalues (from the graph’s adjacency matrix) whose sum and product are integral. It appears that the conjugate pair arises out of the centrality of certain vertices of the graph, which are strongly connected (edgewise) to other vertices of the graph. For example, the wheel graph has a central vertex connected by its spokes to the remaining vertices of the graph. Bipartite graphs have two sets of vertices strongly connected to each other. The vertices of the complete graph are each strongly connected to each other. In this paper we will define a new class of graphs, called q-cliqued graphs, on q
2
+
1 vertices, involving a central vertex connected to q cliques each of order q, and then prove that these q-cliqued graphs are eigen-bi-balanced with respect to a conjugate pair whose sum is -
1 and product 1
-
q. These graphs can be regarded as design graphs, and we use a specific example (q
=
3) in an entomological experiment.


## 2. Construction ofq-Cliqued Graphs

In this section we construct aq-cliqued graph, labelled G
K
q
*, for q
≥
2, and find the associated adjacency matrix for this graph. We take q copies of the complete graph on q vertices K
q, together with a single vertex v, and construct G
K
q
*. Generally, we label the central vertex v and the vertices of the ith copy of (
K
q
)
i as v
1
i
,
v
2
i
,
…
,
v
q
i
,
i
=
1,2
,
…
,
q.


### 2.1. Construction of the 2-Cliqued GraphG
K
2
* and the Associated Adjacency Matrix A
G
K
2
*

Forq
=
2, take 2 copies of K
2, namely, (
K
2
)
1 and (
K
2
)
2, together with a single vertex v. Join v to v
1
i, i
=
1,2, so that v has degree 2 (Figure 1).Figure 1
Construction ofG
K
2
*, (a).Join verticesv
2
1 and v
2
2 of (
K
2
)
1 and (
K
2
)
2 to form three 5-cycles (Figure 2).Figure 2
Construction ofG
K
2
*, (b).Label the central vertexv as vertex v
1 and then for each subclique, label the vertices v
j
i
=
v
1
+
i
-
1
q
+
j, 1
≤
i
≤
2, 1
≤
j
≤
2, that is, v
1
1
=
v
2, v
2
1
=
v
3, v
1
2
=
v
4, and v
2
2
=
v
5. Then the 5
×
5 adjacency matrix of G
K
2
*, where the rows are v
1
,
…
,
v
5and the columns are v
1
,
…
,
v
5, is
(1)
A
G
K
2
*
=
0
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
0
.
By definition of det
⁡
λ
I
-
A
G
K
2
*, the characteristic polynomial of A
G
K
2
* is λ
5
-
5
λ
3
+
5
λ
-
2. The eigenvalues of this adjacency matrix are 2, -
1
+
5
/
2 (twice) and -
1
-
5
/
2 (twice). The conjugate eigenpair is -
1
±
5
/
2. The graph G
K
2
* does not contain a 2-lantern subgraph so it is a design graph, namely, a 2-cliqued design graph.


### 2.2. Construction of the 3-Cliqued GraphG
K
3
* and the Associated Adjacency Matrix A
G
K
3
*

Forq
=
3, take 3 copies of K
3, namely, (
K
3
)
1, (
K
3
)
2, and (
K
3
)
3, together with a single central vertex v. Join v to v
1
i, i
=
1,2
,
3. Join the remaining vertices of the 3 copies of K
3 to form three 5-cycles, that is, v
3
1 and v
2
2, v
3
2 and v
2
3, v
3
3, and v
2
1 (Figure 3).Figure 3
Construction ofG
K
3
*, (b).Label the central vertexv as vertex v
1 and then, for each subclique, label the vertices v
j
i
=
v
1
+
i
-
1
q
+
j, 1
≤
i
≤
3, 1
≤
j
≤
3, that is, v
1
1
=
v
2, v
2
1
=
v
3, v
3
1
=
v
4, v
1
2
=
v
5, v
2
2
=
v
6, v
3
2
=
v
7, v
1
3
=
v
8, v
2
3
=
v
9, and v
3
3
=
v
10. Then the 10
×
10 adjacency matrix of G
K
3
*, where the rows are v
1
,
…
,
v
10and the columns are v
1
,
…
,
v
10, is
(2)
A
G
K
3
*
=
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
1
0
.
All blank elements are zero. The characteristic polynomial of A
G
K
3
* is λ
10
-
15
λ
8
-
6
λ
7
+
75
λ
6
+
48
λ
5
-
144
λ
4
-
114
λ
3
+
75
λ
2
+
68
λ
+
12. The eigenvalues of this adjacency matrix are 3, 1, −2 (twice), 1.879 (twice), −0.347 (twice), and −1.532 (twice). The conjugate eigenpair is -
1
±
9
/
2. The graph G
K
3
* does not contain a 3-lantern subgraph so it is a design graph, namely, a 3-cliqued design graph.


### 2.3. General Construction of theq-Cliqued Graph G
K
q
* and the Associated Adjacency Matrix A
G
K
q
*

For the general construction withq
≥
4, take q copies of K
q, namely, (
K
q
)
1
,
(
K
q
)
2
,
…
,
(
K
q
)
q, where the vertices of (
K
q
)
i are labelled v
j
i, 1
≤
i
≤
q and 1
≤
j
≤
q. Then take a single central vertex v and construct the q-cliqued graph G
K
q
* as follows.(1)
Joinv to v
1
i, 1
≤
i
≤
q.
(2)
Joinv
q
i, the qth vertex of clique i, to v
2
i
+
1, the 2nd vertex in clique i
+
1, for 1
≤
i
≤
q
-
1. Join v
q
q, the qth vertex of clique q, to v
2
1, the 2nd vertex in the 1st clique.
(3)
Ifq
≥
5, join v
j
i, the jth vertex in clique i, to v
j
-
1
i
+
1, the (
j
-
1
)th vertex in clique i
+
1, for all 4
≤
j
≤
q
-
1, where j is even, and for 1
≤
i
≤
q
-
1. Also join v
j
q, the jth vertex in clique q, to v
j
-
1
1, the (
j
-
1
)th vertex in the 1st clique, for all 4
≤
j
≤
q
-
1, where j is even.
(4)
Ifq is even, join v
q
-
1
i, the q
-
1th vertex of clique i, to v
q
-
1
i
+
1, the q
-
1th vertex of clique i
+
1, for all i
≤
q
-
1, where i is odd.Label the central vertexv as vertex v
1, and then for each subclique, label the vertices v
j
i
=
v
1
+
i
-
1
q
+
j, 1
≤
i
≤
q, 1
≤
j
≤
q. Then, the 1
+
q
2
×
1
+
q
2 adjacency matrix A
G
K
q
* of G
K
q
*, with rows v
1
,
v
2
,
…
,
v
1
+
q
2 and columns v
1
,
v
2
,
…
,
v
1
+
q
2, has entries as follows.(1)
The diagonal entries ofA
G
K
q
* are zero; that is, a
i
,
i
=
0, 1
≤
i
≤
1
+
q
2.
(2)
Theq subcliques yield
(3)
a
1
+
i
-
1
q
+
k
,
1
+
i
-
1
q
+
l
=
0
,
1
≤
i
≤
q
,
1
≤
k
≤
q
,
1
≤
l
≤
q
,
k
=
l
,
a
1
+
i
-
1
q
+
k
,
1
+
i
-
1
q
+
l
=
1
,
1
≤
i
≤
q
,
1
≤
k
≤
q
,
1
≤
l
≤
q
,
k
≠
l
.
(3)
Step (1) in the construction (joinv to v
1
i) yields
(4)
a
1,1
+
i
-
1
q
+
1
=
1
,
1
≤
i
≤
q
,
a
1
+
i
-
1
q
+
1,1
=
1
,
1
≤
i
≤
q
.
(4)
Step (2) in the construction (joinv
q
i to v
2
i
+
1) yields
(5)
a
1
+
i
-
1
q
+
q
,
1
+
(
i
+
1
-
1
)
q
+
2
=
a
1
+
i
q
,
3
+
i
q
=
1
,
1
≤
i
≤
q
,
a
1
+
(
i
+
1
-
1
)
q
+
2,1
+
i
-
1
q
+
q
=
a
3
+
i
q
,
1
+
i
q
=
1
,
1
≤
i
≤
q
.
(5)
Ifq
≥
5, step (3) in the construction (join v
j
i to v
j
-
1
i
+
1) yields
a
1
+
i
-
1
q
+
j
,
k
=
1, where k
=
1
+
i
+
1
-
1
q
+
j
-
1
=
i
q
+
j, 1
≤
i
≤
q, 4
≤
j
≤
q
-
1, and j is even.
Ifk
>
1
+
q
2, then m
=
k
-
1
+
q
2 and a
1
+
i
-
1
q
+
j
,
m
=
1.
a
k
,
1
+
i
-
1
q
+
j
=
1, where k
=
1
+
i
+
1
-
1
q
+
j
-
1
=
i
q
+
j, 1
≤
i
≤
q, 4
≤
j
≤
q
-
1, and j is even.
Ifk
>
1
+
q
2, then m
=
k
-
1
+
q
2 and a
m
,
1
+
i
-
1
q
+
j
=
1.
(6)
Ifq is even, step (4) in the construction (join v
q
-
1
i to v
q
-
1
i
+
1) yields
a
1
+
i
-
1
q
+
q
-
1
,
l
=
a
i
q
,
l
=
1, where l
=
1
+
i
+
1
-
1
q
+
q
-
1
=
i
+
1
q, 1
≤
i
≤
q, and i is odd.
Ifl
>
1
+
q
2, then n
=
l
-
1
+
q
2 and a
i
q
,
n
=
1.
a
l
,
1
+
i
-
1
q
+
q
-
1
=
a
l
,
i
q
=
1, where l
=
1
+
i
-
1
+
1
q
+
q
-
1
=
i
+
1
q, 1
≤
i
≤
q, and i is odd.
Ifl
>
1
+
q
2, then n
=
l
-
1
+
q
2 and a
n
,
i
q
=
1.
(7)
For all other entries inA
G
K
q
*, a
i
,
j
=
0, 1
≤
i
≤
1
+
q
2 and 1
≤
j
≤
1
+
q
2.


## 2.1. Construction of the 2-Cliqued GraphG
K
2
* and the Associated Adjacency Matrix A
G
K
2
*

Forq
=
2, take 2 copies of K
2, namely, (
K
2
)
1 and (
K
2
)
2, together with a single vertex v. Join v to v
1
i, i
=
1,2, so that v has degree 2 (Figure 1).Figure 1
Construction ofG
K
2
*, (a).Join verticesv
2
1 and v
2
2 of (
K
2
)
1 and (
K
2
)
2 to form three 5-cycles (Figure 2).Figure 2
Construction ofG
K
2
*, (b).Label the central vertexv as vertex v
1 and then for each subclique, label the vertices v
j
i
=
v
1
+
i
-
1
q
+
j, 1
≤
i
≤
2, 1
≤
j
≤
2, that is, v
1
1
=
v
2, v
2
1
=
v
3, v
1
2
=
v
4, and v
2
2
=
v
5. Then the 5
×
5 adjacency matrix of G
K
2
*, where the rows are v
1
,
…
,
v
5and the columns are v
1
,
…
,
v
5, is
(1)
A
G
K
2
*
=
0
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
0
.
By definition of det
⁡
λ
I
-
A
G
K
2
*, the characteristic polynomial of A
G
K
2
* is λ
5
-
5
λ
3
+
5
λ
-
2. The eigenvalues of this adjacency matrix are 2, -
1
+
5
/
2 (twice) and -
1
-
5
/
2 (twice). The conjugate eigenpair is -
1
±
5
/
2. The graph G
K
2
* does not contain a 2-lantern subgraph so it is a design graph, namely, a 2-cliqued design graph.


## 2.2. Construction of the 3-Cliqued GraphG
K
3
* and the Associated Adjacency Matrix A
G
K
3
*

Forq
=
3, take 3 copies of K
3, namely, (
K
3
)
1, (
K
3
)
2, and (
K
3
)
3, together with a single central vertex v. Join v to v
1
i, i
=
1,2
,
3. Join the remaining vertices of the 3 copies of K
3 to form three 5-cycles, that is, v
3
1 and v
2
2, v
3
2 and v
2
3, v
3
3, and v
2
1 (Figure 3).Figure 3
Construction ofG
K
3
*, (b).Label the central vertexv as vertex v
1 and then, for each subclique, label the vertices v
j
i
=
v
1
+
i
-
1
q
+
j, 1
≤
i
≤
3, 1
≤
j
≤
3, that is, v
1
1
=
v
2, v
2
1
=
v
3, v
3
1
=
v
4, v
1
2
=
v
5, v
2
2
=
v
6, v
3
2
=
v
7, v
1
3
=
v
8, v
2
3
=
v
9, and v
3
3
=
v
10. Then the 10
×
10 adjacency matrix of G
K
3
*, where the rows are v
1
,
…
,
v
10and the columns are v
1
,
…
,
v
10, is
(2)
A
G
K
3
*
=
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
1
0
.
All blank elements are zero. The characteristic polynomial of A
G
K
3
* is λ
10
-
15
λ
8
-
6
λ
7
+
75
λ
6
+
48
λ
5
-
144
λ
4
-
114
λ
3
+
75
λ
2
+
68
λ
+
12. The eigenvalues of this adjacency matrix are 3, 1, −2 (twice), 1.879 (twice), −0.347 (twice), and −1.532 (twice). The conjugate eigenpair is -
1
±
9
/
2. The graph G
K
3
* does not contain a 3-lantern subgraph so it is a design graph, namely, a 3-cliqued design graph.


## 2.3. General Construction of theq-Cliqued Graph G
K
q
* and the Associated Adjacency Matrix A
G
K
q
*

For the general construction withq
≥
4, take q copies of K
q, namely, (
K
q
)
1
,
(
K
q
)
2
,
…
,
(
K
q
)
q, where the vertices of (
K
q
)
i are labelled v
j
i, 1
≤
i
≤
q and 1
≤
j
≤
q. Then take a single central vertex v and construct the q-cliqued graph G
K
q
* as follows.(1)
Joinv to v
1
i, 1
≤
i
≤
q.
(2)
Joinv
q
i, the qth vertex of clique i, to v
2
i
+
1, the 2nd vertex in clique i
+
1, for 1
≤
i
≤
q
-
1. Join v
q
q, the qth vertex of clique q, to v
2
1, the 2nd vertex in the 1st clique.
(3)
Ifq
≥
5, join v
j
i, the jth vertex in clique i, to v
j
-
1
i
+
1, the (
j
-
1
)th vertex in clique i
+
1, for all 4
≤
j
≤
q
-
1, where j is even, and for 1
≤
i
≤
q
-
1. Also join v
j
q, the jth vertex in clique q, to v
j
-
1
1, the (
j
-
1
)th vertex in the 1st clique, for all 4
≤
j
≤
q
-
1, where j is even.
(4)
Ifq is even, join v
q
-
1
i, the q
-
1th vertex of clique i, to v
q
-
1
i
+
1, the q
-
1th vertex of clique i
+
1, for all i
≤
q
-
1, where i is odd.Label the central vertexv as vertex v
1, and then for each subclique, label the vertices v
j
i
=
v
1
+
i
-
1
q
+
j, 1
≤
i
≤
q, 1
≤
j
≤
q. Then, the 1
+
q
2
×
1
+
q
2 adjacency matrix A
G
K
q
* of G
K
q
*, with rows v
1
,
v
2
,
…
,
v
1
+
q
2 and columns v
1
,
v
2
,
…
,
v
1
+
q
2, has entries as follows.(1)
The diagonal entries ofA
G
K
q
* are zero; that is, a
i
,
i
=
0, 1
≤
i
≤
1
+
q
2.
(2)
Theq subcliques yield
(3)
a
1
+
i
-
1
q
+
k
,
1
+
i
-
1
q
+
l
=
0
,
1
≤
i
≤
q
,
1
≤
k
≤
q
,
1
≤
l
≤
q
,
k
=
l
,
a
1
+
i
-
1
q
+
k
,
1
+
i
-
1
q
+
l
=
1
,
1
≤
i
≤
q
,
1
≤
k
≤
q
,
1
≤
l
≤
q
,
k
≠
l
.
(3)
Step (1) in the construction (joinv to v
1
i) yields
(4)
a
1,1
+
i
-
1
q
+
1
=
1
,
1
≤
i
≤
q
,
a
1
+
i
-
1
q
+
1,1
=
1
,
1
≤
i
≤
q
.
(4)
Step (2) in the construction (joinv
q
i to v
2
i
+
1) yields
(5)
a
1
+
i
-
1
q
+
q
,
1
+
(
i
+
1
-
1
)
q
+
2
=
a
1
+
i
q
,
3
+
i
q
=
1
,
1
≤
i
≤
q
,
a
1
+
(
i
+
1
-
1
)
q
+
2,1
+
i
-
1
q
+
q
=
a
3
+
i
q
,
1
+
i
q
=
1
,
1
≤
i
≤
q
.
(5)
Ifq
≥
5, step (3) in the construction (join v
j
i to v
j
-
1
i
+
1) yields
a
1
+
i
-
1
q
+
j
,
k
=
1, where k
=
1
+
i
+
1
-
1
q
+
j
-
1
=
i
q
+
j, 1
≤
i
≤
q, 4
≤
j
≤
q
-
1, and j is even.
Ifk
>
1
+
q
2, then m
=
k
-
1
+
q
2 and a
1
+
i
-
1
q
+
j
,
m
=
1.
a
k
,
1
+
i
-
1
q
+
j
=
1, where k
=
1
+
i
+
1
-
1
q
+
j
-
1
=
i
q
+
j, 1
≤
i
≤
q, 4
≤
j
≤
q
-
1, and j is even.
Ifk
>
1
+
q
2, then m
=
k
-
1
+
q
2 and a
m
,
1
+
i
-
1
q
+
j
=
1.
(6)
Ifq is even, step (4) in the construction (join v
q
-
1
i to v
q
-
1
i
+
1) yields
a
1
+
i
-
1
q
+
q
-
1
,
l
=
a
i
q
,
l
=
1, where l
=
1
+
i
+
1
-
1
q
+
q
-
1
=
i
+
1
q, 1
≤
i
≤
q, and i is odd.
Ifl
>
1
+
q
2, then n
=
l
-
1
+
q
2 and a
i
q
,
n
=
1.
a
l
,
1
+
i
-
1
q
+
q
-
1
=
a
l
,
i
q
=
1, where l
=
1
+
i
-
1
+
1
q
+
q
-
1
=
i
+
1
q, 1
≤
i
≤
q, and i is odd.
Ifl
>
1
+
q
2, then n
=
l
-
1
+
q
2 and a
n
,
i
q
=
1.
(7)
For all other entries inA
G
K
q
*, a
i
,
j
=
0, 1
≤
i
≤
1
+
q
2 and 1
≤
j
≤
1
+
q
2.


## 3. Eigenvalues ofq-Cliqued Graphs

In this section, we focus on theq-cliqued graphs as constructed in Section 2. We show that the q-cliqued graphs have eigenvalue q and conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2. The determination of the conjugate eigenpair is equivalent to showing that the cubic
(6)
λ
3
-
λ
2
(
q
-
1
)
-
λ
q
-
λ
q
-
1
+
q
(
q
-
1
)
=
λ
-
q
λ
2
+
λ
-
q
-
1
is a factor of the characteristic equation determined by A
G
q
*
x
_
=
λ
x
_, where A
G
q
* is the adjacency matrix of the q-cliqued graph G
q
*.The proof requires a number of specific definitions of vertices within theq-clique graph, and we use the connectivity between the first clique, the second to last clique, and the last clique in the proof of the conjugate eigenpair. The central vertex also plays a key role in this proof, as each subclique K
q is connected to the central vertex. The proof of determining the conjugate eigenpair is determined explicitly for the cases q
=
4 and q
=
5, and then it is generalized for the q-cliqued graph.Once we have found the conjugate eigenpair of theq-cliqued graph, we then determine the eigen-bi-balanced properties of the class of q-cliqued graphs associated with this eigenpair in Section 4. The values of all the newly defined eigen-bi-balanced properties, as defined in Winter and Jessop [4], are easily determined for this class of graphs.Theorem 1.
Theq-cliqued graphs, as constructed in Section 1, have eigenvalues λ
=
q (and the q-cliqued graph is q-regular) and conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2. The conjugate eigenpair arises out of the “tightness” of the connection between the central vertex and the cliques and between two adjacent cliques—for convention we chose the second last and last clique.


### 3.1. Proof of Theorem1

We will show Theorem1, for q
=
4 and q
=
5, and then give the general proof for all q
≥
6. Illustration of cases q
=
2 and q
=
3 can be found in Jessop [5]. First, we need the following definitions.


#### 3.1.1. Notation Convention

(1)
LetA
G
K
q
* be the adjacency matrix of the q-cliqued graph G
K
q
*. Let x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T be an eigenvector of A
G
K
q
*, corresponding to the eigenvalue λ. Then A
G
K
q
*
x
_
=
λ
x
_.
(2)
Ifx
i is the ith entry in x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1, then we say that x
i corresponds to the ith vertex v
i in G
K
q
* and vice versa.
(3)
The first entry inx
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T is x
1, the second entry is x
2, and the third entry is x
3.
(4)
The set of vertices in the first cliqueK
q
1 is v
2
,
v
3
,
…
,
v
q
,
v
q
+
1 and the corresponding set of entries in x
_ is x
2
,
x
3
,
…
,
x
q
,
x
q
+
1.
(5)
The anchor vertex of each clique is the vertex in each clique which is joined to the first vertexv
1. The anchor vertex of the last clique is v
a
=
v
2
+
q
(
q
-
1
), and the anchor vertex of the second to last clique is v
a
-
q
=
v
2
+
q
(
q
-
2
).
(6)
The switching pair of entries inx
_ is x
q
2
-
1
=
x
l
-
2 (third last entry in x
_) and x
q
2
=
x
l
-
1 (second last entry in x
_).
(7)
The last entry inx
_ is x
l
=
x
q
2
+
1.


#### 3.1.2. The Generating Set

LetT
=
{
v
1
,
v
2
} and let U be the set of vertices of the second last clique which are adjacent to vertices in the last clique, that is, U
=
v
u
1
,
v
u
2
,
…
,
v
u
t, where t
=
q
-
1
/
2, when q is odd, or t
=
q
/
2, when q is even. Let S
=
T
∪
U be the generating set of vertices. Then, if S
=
v
1
,
v
2
,
v
u
1
,
v
u
2
,
…
,
v
u
t, we define ∑
S
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t where x
1
,
x
2
,
x
u
1
,
x
u
2
,
…
,
x
u
t are the entries in x
_ which correspond to the vertices in S.


#### 3.1.3. The Two Main Equations That Generate the Conjugate Eigenpairs

We will use the relationshipA
G
K
q
*
x
_
=
λ
x
_ to determine the two main equations that generate the conjugate eigenpairs as follows:
(7)
∑
S
=
λ
2
x
l
-
q
x
l
,
(8)
λ
∑
S
=
q
-
1
∑
S
+
q
-
1
x
l
⟹
∑
S
=
q
-
1
x
l
λ
-
q
-
1
.
Substitute (8) into (7) to get (
q
-
1
)
λ
x
l
/
λ
-
(
q
-
1
)
=
λ
2
x
l
-
q
x
l, λ
≠
q
-
1, so that
(9)
q
-
1
λ
=
λ
2
λ
-
q
-
1
-
q
λ
-
q
-
1
⟹
λ
3
-
λ
2
(
q
-
1
)
-
q
λ
+
q
(
q
-
1
)
-
λ
(
q
-
1
)
=
0
⟹
(
λ
-
q
)
(
λ
2
+
λ
-
(
q
-
1
)
)
=
0
.
This gives us three eigenvalues, namely, λ
=
q and the conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2.


#### 3.1.4. The Caseq
=
4

Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
17
T be an eigenvector of G
K
4
*. Then A
G
K
4
*
x
_
=
λ
x
_ gives
(10)
x
2
+
x
6
+
x
10
+
x
14
x
3
+
x
4
+
x
5
+
x
1
x
2
+
x
4
+
x
5
+
x
17
x
3
+
x
5
+
x
2
+
x
8
x
2
+
x
3
+
x
4
+
x
7
x
1
+
x
7
+
x
8
+
x
9
x
5
+
x
6
+
x
8
+
x
9
x
4
+
x
6
+
x
7
+
x
9
x
6
+
x
7
+
x
8
+
x
11
x
1
+
x
11
+
x
12
+
x
13
x
9
+
x
10
+
x
12
+
x
13
x
10
+
x
11
+
x
13
+
x
16
x
10
+
x
11
+
x
12
+
x
15
x
1
+
x
15
+
x
16
+
x
17
x
13
+
x
14
+
x
16
+
x
17
x
12
+
x
14
+
x
15
+
x
17
x
3
+
x
14
+
x
15
+
x
16
=
λ
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
11
x
12
x
13
x
14
x
15
x
16
x
17
.
Taking the last equation, we get
(11)
x
3
+
x
14
+
x
15
+
x
16
=
λ
x
17
⟹
λ
x
3
+
x
14
+
x
15
+
x
16
=
λ
λ
x
17
⟹
λ
x
3
+
λ
x
14
+
λ
x
15
+
λ
x
16
=
λ
2
x
17
.
Expand the left hand side, using the equations corresponding to the neighbours of v
3, v
14, v
15, and v
16 to get
(12)
(
x
2
+
x
4
+
x
5
+
x
17
)
+
(
x
1
+
x
15
+
x
16
+
x
17
)
+
(
x
13
+
x
14
+
x
16
+
x
17
)
+
(
x
12
+
x
14
+
x
15
+
x
17
)
=
λ
2
x
17
⟹
x
1
+
x
2
+
x
4
+
x
5
+
2
(
x
14
+
x
15
+
x
16
)
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
.
Step 2. Put x
16
=
-
x
15 (second and third to last entries of x
_ have opposite signs and are called the switching pair). Then we have
(13)
x
1
+
x
2
+
x
4
+
x
5
+
2
x
14
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
.
Let T
=
v
1
,
v
2 and let U be the set of all vertices that belong to the second last clique, which are neighbours of the last clique; that is, U
=
v
12
,
v
13. Then the generating set S
=
T
∪
U
=
{
v
1
,
v
2
}
∪
v
12
,
v
13
=
{
v
1
,
v
2
,
v
12
,
v
13
}.Step 3. Set x
4
=
x
5
=
x
14
=
0; then
(14)
x
1
+
x
2
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
⟹
x
1
+
x
2
+
x
12
+
x
13
=
λ
2
x
17
-
4
x
17
⟹
∑
S
=
λ
2
x
17
-
4
x
17
.
This verifies (7) of Section 3.1.2 for the case q
=
4.Step 4. Take the neighbours of the vertices in S
=
v
1
,
v
2
,
v
12
,
v
13 to get
(15)
(
x
2
+
x
6
+
x
10
+
x
14
)
+
(
x
1
+
x
3
+
x
4
+
x
5
)
+
(
x
10
+
x
11
+
x
13
+
x
16
)
+
(
x
10
+
x
11
+
x
12
+
x
15
)
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
.
From above, x
4
=
x
5
=
x
14
=
0, and x
16
=
-
x
15, so that
(16)
x
2
+
x
6
+
x
10
+
x
1
+
x
3
+
x
10
+
x
11
+
x
13
+
x
10
+
x
11
+
x
12
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
x
3
+
x
6
+
3
x
10
+
2
x
11
+
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
.
Now set x
3
=
2
x
1, x
6
=
2
x
13, x
10
=
λ
x
17, x
11
=
x
2, and x
12
=
0. Then
(17)
x
1
+
x
2
+
x
3
+
x
6
+
3
x
10
+
2
x
11
+
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
2
x
1
+
2
x
13
+
3
λ
x
17
+
2
x
2
+
3
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
3
x
1
+
3
x
2
+
3
x
12
+
3
x
13
+
3
λ
x
17
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
3
(
x
1
+
x
2
+
x
12
+
x
13
)
+
3
λ
x
17
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
x
12
+
x
13
=
3
λ
x
17
λ
-
3
⟹
∑
S
=
3
λ
x
17
λ
-
3
.
This verifies (8) of Section 3.1.2 for the case q
=
4.Step 5. Substitute (17) into (14) to get
(18)
3
λ
x
17
λ
-
3
=
λ
2
x
17
-
4
x
17
⟹
λ
2
(
λ
-
3
)
x
17
-
4
(
λ
-
3
)
x
17
=
3
λ
x
17
⟹
λ
3
x
17
-
3
λ
2
x
17
-
4
λ
x
26
+
12
x
17
-
3
λ
x
17
=
0
⟹
λ
3
x
17
-
3
λ
2
x
17
-
7
λ
x
26
+
12
x
17
=
0
⟹
(
λ
-
4
)
(
λ
2
+
λ
-
3
)
x
17
=
0
⟹
λ
=
4
or
λ
=
-
1
±
1
-
4
-
3
2
=
-
1
±
13
2
.
So we have eigenvalues λ
=
4 (which is the same as the degree of the vertices in the 4-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
13
/
2.


#### 3.1.5. The Caseq
=
5

Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
26
T be an eigenvector of G
K
5
*. Then the last equation from A
G
K
5
*
x
_
=
λ
x
_ gives
(19)
x
3
+
x
22
+
x
23
+
x
24
+
x
25
=
λ
x
26
⟹
λ
x
3
+
x
22
+
x
23
+
x
24
+
x
25
=
λ
λ
x
26
⟹
λ
x
3
+
λ
x
22
+
λ
x
23
+
λ
x
24
+
λ
x
25
=
λ
2
x
26
.
Expand the left hand side, using the equations corresponding to the neighbours of v
3, v
22, v
23, v
24, and v
25 to get
(20)
x
2
+
x
4
+
x
5
+
x
6
+
x
26
+
x
1
+
x
23
+
x
24
+
x
25
+
x
26
+
x
21
+
x
22
+
x
24
+
x
25
+
x
26
+
x
20
+
x
22
+
x
23
+
x
25
+
x
26
+
x
4
+
x
22
+
x
23
+
x
24
+
x
26
=
λ
2
x
26
⟹
x
1
+
x
2
+
2
x
4
+
x
5
+
x
6
+
x
20
+
x
21
+
3
x
22
+
3
x
23
+
3
x
24
+
3
x
25
+
5
x
26
=
λ
2
x
26
.Step 2. Put x
25
=
-
x
24 (second and third to last entries of x
_ have opposite signs and are called the switching pair). Set T
=
v
1
,
v
2 and U
=
{all vertices in S that belong to the second last clique, which are neighbours of the last clique}
=
v
20
,
v
21. Then the generating set S
=
T
∪
U
=
{
v
1
,
v
2
}
∪
v
20
,
v
21
=
{
v
1
,
v
2
,
v
20
,
v
21
}.Then we havex
1
+
x
2
+
2
x
4
+
x
5
+
x
6
+
x
20
+
x
21
+
3
x
22
+
3
x
23
+
5
x
26
=
λ
2
x
26.Step 3. Put x
4
=
x
5
=
0, x
6
=
-
3
x
22, and x
23
=
0, so we have
(21)
x
1
+
x
2
+
x
20
+
x
21
+
5
x
26
=
λ
2
x
26
⟹
x
1
+
x
2
+
x
20
+
x
21
=
λ
2
x
26
-
5
x
26
⟹
∑
S
=
λ
2
x
26
-
5
x
26
.
This verifies (7) of Section 3.1.2 for the case q
=
5.Step 4. Take the neighbours of the vertices in S
=
v
1
,
v
2
,
v
20
,
v
21 to get
(22)
x
2
+
x
7
+
x
12
+
x
17
+
x
22
+
x
1
+
x
3
+
x
4
+
x
5
+
x
6
+
x
17
+
x
18
+
x
19
+
x
21
+
x
24
+
x
17
+
x
18
+
x
19
+
x
20
+
x
23
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
From above, x
4
=
x
5
=
0, x
6
=
-
3
x
22, x
23
=
0, and x
25
=
-
x
24 so that
(23)
x
2
+
x
7
+
x
12
+
x
17
+
x
22
+
x
1
+
x
3
-
3
x
22
+
x
17
+
x
18
+
x
19
+
x
21
+
x
24
+
x
17
+
x
18
+
x
19
+
x
20
=
λ
x
1
+
x
2
+
x
20
+
x
21
⟹
x
1
+
x
2
+
x
3
+
x
7
+
x
12
+
3
x
17
+
3
x
18
+
2
x
19
+
x
20
+
x
21
-
2
x
22
+
x
24
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
Now set x
3
=
3
x
2, x
7
=
3
x
1, x
12
=
4
λ
x
26, x
17
=
0, x
18
=
3
/
2
x
20, x
19
=
3
/
2
x
21, and x
24
=
2
x
22. Then
(24)
x
1
+
x
2
+
x
3
+
x
7
+
x
12
+
3
x
17
+
2
x
18
+
2
x
19
+
x
20
+
x
21
-
2
x
22
+
x
24
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
⟹
x
1
+
x
2
+
3
x
2
+
3
x
1
+
4
λ
x
26
+
3
x
20
+
3
x
21
+
x
20
+
x
21
-
2
x
22
+
2
x
22
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
⟹
4
x
1
+
4
x
2
+
4
x
20
+
4
x
21
+
4
λ
x
26
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
⟹
x
1
+
x
2
+
x
20
+
x
21
=
4
x
26
λ
-
4
⟹
∑
S
=
4
x
26
λ
-
4
.
This verifies (8) of Section 3.1.2 for the case q
=
5.Step 5. Substitute (24) into (21) to get
(25)
4
λ
x
26
λ
-
4
=
λ
2
x
26
-
5
x
26
⟹
λ
2
(
λ
-
4
)
x
26
-
5
(
λ
-
4
)
x
26
=
4
λ
x
26
⟹
λ
3
x
26
-
4
λ
2
x
26
-
5
λ
x
26
+
20
x
26
-
4
λ
x
26
=
0
⟹
λ
3
x
26
-
4
λ
2
x
26
-
9
λ
x
26
+
20
x
26
=
0
⟹
(
λ
-
5
)
(
λ
2
+
λ
-
4
)
x
26
=
0
⟹
λ
=
5
or
λ
=
-
1
±
1
-
4
-
4
2
=
-
1
±
17
2
.
So we have eigenvalues λ
=
5 (which is the same as the degree of the vertices in the 5-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
17
/
2.


#### 3.1.6. Eigenvalues of General Case

Refer to Section3.1.1 for the vertex notation and definitions. We require the following additional definitions to clarify the proof for the general case, where q
≥
6.(1)
λ
x
l is equal to the sum of the entries in x
_ whose corresponding vertices are adjacent to v
l in G
K
q
*; that is, λ
x
l
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1 as v
l is adjacent to the set of vertices v
3
,
v
a
,
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
,
v
l
-
21
,
v
l
-
1 in G
K
q
*.
(2)
Let the neighbours ofv
l be N
v
l
=
v
l
1
,
v
l
2
,
…
,
v
l
q
=
v
3
,
v
a
,
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
,
v
l
-
2
,
v
l
-
1. Then, as per (7) above, λ
x
l is equal to the sum of the entries in x
_ whose corresponding vertices are in N
v
l; that is, λ
x
l
=
x
l
1
+
x
l
2
+
⋯
+
x
l
q
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1.
(3)
LetN
N
v
l be the set of vertices which are adjacent to the vertices in N
v
l in G
K
q
*. Then λ
λ
x
l is the sum of the entries in x
_ whose corresponding vertices are in N
N
v
l.
(4)
LetQ be the set of vertices {
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
} which all belong to the last clique. Set x
k
=
0 for all v
k
∈
Q. Note that v
l
-
2
,
v
l
-
1
,
v
l
∉
Q.
(5)
The set of neighbours ofv
a is v
1
,
v
l
-
2
,
v
l
-
1
,
v
l, together with the set of vertices in Q.
(6)
Lett
=
q
-
1
/
2
;
q
odd
q
/
2
;
q
even
. and let R be the set of vertices from N
N
v
l which belong to the first clique, which are neighbours of vertices in the last clique. Then R
=
v
r
1
,
v
r
2
,
…
,
v
r
q
-
2
-
t
=
v
4
,
v
6
,
v
8
,
…
,
v
q
-
1.
(7)
LetU be the set of vertices from N
N
v
l which belong to the second last q
-
1th clique, which are neighbours of the vertices from the last qth clique. Then U
=
v
u
1
,
v
u
2
,
…
,
v
u
t.
(8)
LetT
=
{
v
1
,
v
2
}.
(9)
LetS be the generating set of vertices; then S
=
T
∪
U, and ∑
S
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t.
(10)
LetP be the set of vertices in the second last clique, excluding the anchor vertex, which are not neighbours of the last clique and are therefore not in U as defined above. Then P
=
v
p
1
,
v
p
2
,
…
,
v
p
q
-
1
-
t.
(11)
LetW be the subset of vertices in the last clique, whose vertices join backwards to vertices of U. Then W
=
v
w
1
,
v
w
2
,
…
,
v
w
t
=
v
a
+
1
,
v
a
+
2
,
v
a
+
4
,
…
,
v
a
+
q
-
3
=
v
l
-
2.Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T be an eigenvector of G
K
q
*. Then the last equation of A
G
K
q
*
x
_
=
λ
x
_ gives
(26)
λ
x
l
=
x
l
1
+
x
2
+
⋯
+
x
l
q
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1
.
So,
(27)
λ
2
x
l
=
λ
λ
x
l
=
λ
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1
=
λ
x
3
+
λ
x
a
+
λ
x
a
+
1
+
λ
x
a
+
2
+
⋯
+
λ
x
l
-
3
+
λ
x
l
-
2
+
λ
x
l
-
1
=
x
1
+
x
2
+
x
4
+
x
5
+
⋯
+
x
q
+
x
q
+
1
+
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
1
,
(
q
-
2
)
x
a
+
2
+
⋯
+
(
q
-
2
)
x
a
+
t
+
⋯
+
(
q
-
2
)
x
l
-
3
+
(
q
-
2
)
x
l
-
2
+
(
q
-
2
)
x
l
-
1
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
x
r
1
+
x
r
2
+
⋯
+
x
r
q
-
2
-
t
.Step 2. Set x
l
-
1
=
-
x
l
-
2 (switching entries).Step 3. Set x
4
=
x
5
=
⋯
=
x
q
=
0. This implies x
r
1
=
x
r
2
=
⋯
=
x
r
q
-
2
-
t
=
0. Set x
k
=
0 for all v
k
∈
Q, and set x
q
+
1
=
-
(
q
-
2
)
x
a. Then
(28)
λ
2
x
l
=
x
1
+
x
2
+
x
4
+
x
5
+
⋯
+
x
q
+
x
q
+
1
+
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
1
,
(
q
-
2
)
x
a
+
2
+
⋯
+
(
q
-
2
)
x
a
+
t
+
⋯
+
(
q
-
2
)
x
l
-
3
+
(
q
-
2
)
x
l
-
2
+
(
q
-
2
)
x
l
-
1
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
x
r
1
+
x
r
2
+
⋯
+
x
r
q
-
2
-
t
=
x
1
+
x
2
+
0
+
0
+
⋯
+
0
-
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
0
+
0
+
⋯
+
0
+
0
+
(
q
-
2
)
x
l
-
2
-
(
q
-
2
)
x
l
-
2
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
(
0
+
0
+
⋯
+
0
)
⟹
λ
2
x
l
=
x
1
+
x
2
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
⟹
λ
2
x
l
-
q
x
l
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
⟹
λ
2
x
l
-
q
x
l
=
∑
S
⟹
∑
S
=
λ
2
x
l
-
q
x
l
.
This verifies (7) of Section 3.1.2 for the general case q.Step 4. Now take the neighbours of the generating set S, where
(29)
S
=
T
∪
U
=
v
1
,
v
2
∪
v
u
1
,
v
u
2
,
…
,
v
u
t
,
where t
=
q
-
1
/
2, if q is odd, and t
=
q
/
2, if q is even.The neighbours ofv
1 are N
v
1
=
v
2
,
v
2
+
q
,
v
2
+
2
q
,
…
,
v
2
+
q
(
q
-
1
). The set of neighbours of v
2 are N
v
2
=
v
1
,
v
3
,
v
4
,
…
,
v
q
+
1. The sum of the entries in x
_ corresponding to the neighbours of the vertices in U is ∑
N
v
u
1
,
v
u
2
,
…
,
v
u
q
-
1
-
t
=
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
∑
W.Then the sum of the entries inx
_ corresponding to the neighbours of the vertices in S is
(30)
λ
∑
S
=
∑
N
S
=
∑
N
v
1
+
∑
N
v
1
+
∑
N
v
u
1
,
v
u
1
,
…
,
v
u
q
-
1
-
t
=
(
x
2
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
)
+
(
x
1
+
x
3
+
x
4
+
⋯
+
x
q
+
x
q
+
1
)
+
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
∑
W
.
As before, set x
l
-
1
=
-
x
l
-
2 and set x
4
=
x
5
=
⋯
=
x
q
=
0. This implies x
r
1
=
x
r
2
=
⋯
=
x
r
q
-
2
-
t
=
0.Setx
k
=
0 for all v
k
∈
Q, and set x
q
+
1
=
-
(
q
-
2
)
x
a. Then,
(31)
λ
∑
S
=
(
x
2
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
)
+
(
x
1
+
x
3
+
0
+
⋯
+
0
-
(
q
-
2
)
x
a
)
+
t
-
1
∑
U
+
t
x
a
-
q
+
t
∑
P
+
0
+
0
+
⋯
+
0
+
x
l
-
2
=
x
1
+
x
2
+
x
3
-
(
q
-
2
)
x
a
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
+
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
x
l
-
2
.
Now set x
3
=
q
-
2
x
2, x
2
+
q
=
q
-
2
x
1, x
2
+
2
q
=
q
-
1
λ
x
l, x
2
+
3
q
=
x
2
+
4
q
=
⋯
=
x
2
+
q
-
2
q
=
0, x
2
+
q
-
1
q
=
x
a, x
a
-
q
=
x
2
+
q
q
-
2
=
0, and x
l
-
2
=
(
q
-
3
)
x
a
=
-
x
l
-
1. Then
(32)
λ
∑
S
=
x
1
+
x
2
+
(
q
-
2
)
x
2
-
(
q
-
2
)
x
a
+
(
q
-
2
)
x
1
+
(
q
-
1
)
λ
x
l
+
0
+
⋯
+
0
+
x
a
+
(
t
-
1
)
∑
U
+
t
0
+
t
∑
P
+
(
q
-
3
)
x
a
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
∑
U
+
t
∑
P
.
Set x
p
1
=
q
-
t
/
t
x
u
1, x
p
2
=
q
-
t
/
t
x
,
…
,
x
p
t
=
q
-
t
/
t
x
u
t, and x
p
(
t
+
1
)
=
0 if q is even, as P has one more vertex than U when q is even. Then,
(33)
λ
∑
S
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
∑
U
+
t
∑
P
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
(
x
k
1
+
x
k
2
+
+
⋯
+
x
k
t
)
+
t
q
-
t
t
(
x
k
1
+
x
k
2
+
⋯
+
x
k
t
)
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
q
-
1
)
(
x
k
1
+
x
k
2
+
+
⋯
+
x
k
t
)
=
(
q
-
1
)
(
x
1
+
x
2
+
x
k
1
+
x
k
2
+
⋯
+
x
k
t
)
+
(
q
-
1
)
λ
x
l
=
(
q
-
1
)
∑
S
+
(
q
-
1
)
λ
x
l
⟹
λ
-
q
-
1
∑
S
=
q
-
1
λ
x
l
⟹
∑
S
=
q
-
1
λ
x
l
λ
-
q
-
1
.
Substituting (33) into (28), we get
(34)
q
-
1
λ
x
l
λ
-
(
q
-
1
)
=
λ
2
x
l
-
q
x
l
⟹
λ
2
(
λ
-
(
q
-
1
)
)
x
l
-
q
(
λ
-
(
q
-
1
)
)
x
l
=
(
q
-
1
)
λ
x
l
⟹
λ
3
x
l
-
(
q
-
1
)
λ
2
x
l
-
q
λ
x
l
+
q
(
q
-
1
)
x
l
-
(
q
-
1
)
λ
x
l
=
0
⟹
λ
3
x
l
-
(
q
-
1
)
λ
2
x
l
-
(
2
q
-
1
)
λ
x
l
+
q
(
q
-
1
)
x
l
=
0
⟹
(
λ
-
q
)
(
λ
2
+
λ
-
(
q
-
1
)
)
x
l
=
0
⟹
λ
=
q
or
λ
=
-
1
±
1
-
(
-
4
(
q
-
1
)
)
2
=
-
1
±
1
+
4
(
q
-
1
)
2
.
So we have eigenvalues λ
=
q (which is the same as the degree of the vertices in the q-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2. This completes the proof of Theorem 1.This concludes the proof of the conjugate eigenpair of the adjacency matrix associated with theq-cliqued graphs, as constructed in Section 2. It is interesting to note that the conjugate eigenpair is a function of the clique number of the graph. It can also be proved that q-cliqued graphs are design graphs—see Jessop [5].In the next section, we determine the eigen-bi-balanced properties ofq-cliqued graphs associated with the conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2.


## 3.1. Proof of Theorem1

We will show Theorem1, for q
=
4 and q
=
5, and then give the general proof for all q
≥
6. Illustration of cases q
=
2 and q
=
3 can be found in Jessop [5]. First, we need the following definitions.


### 3.1.1. Notation Convention

(1)
LetA
G
K
q
* be the adjacency matrix of the q-cliqued graph G
K
q
*. Let x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T be an eigenvector of A
G
K
q
*, corresponding to the eigenvalue λ. Then A
G
K
q
*
x
_
=
λ
x
_.
(2)
Ifx
i is the ith entry in x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1, then we say that x
i corresponds to the ith vertex v
i in G
K
q
* and vice versa.
(3)
The first entry inx
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T is x
1, the second entry is x
2, and the third entry is x
3.
(4)
The set of vertices in the first cliqueK
q
1 is v
2
,
v
3
,
…
,
v
q
,
v
q
+
1 and the corresponding set of entries in x
_ is x
2
,
x
3
,
…
,
x
q
,
x
q
+
1.
(5)
The anchor vertex of each clique is the vertex in each clique which is joined to the first vertexv
1. The anchor vertex of the last clique is v
a
=
v
2
+
q
(
q
-
1
), and the anchor vertex of the second to last clique is v
a
-
q
=
v
2
+
q
(
q
-
2
).
(6)
The switching pair of entries inx
_ is x
q
2
-
1
=
x
l
-
2 (third last entry in x
_) and x
q
2
=
x
l
-
1 (second last entry in x
_).
(7)
The last entry inx
_ is x
l
=
x
q
2
+
1.


### 3.1.2. The Generating Set

LetT
=
{
v
1
,
v
2
} and let U be the set of vertices of the second last clique which are adjacent to vertices in the last clique, that is, U
=
v
u
1
,
v
u
2
,
…
,
v
u
t, where t
=
q
-
1
/
2, when q is odd, or t
=
q
/
2, when q is even. Let S
=
T
∪
U be the generating set of vertices. Then, if S
=
v
1
,
v
2
,
v
u
1
,
v
u
2
,
…
,
v
u
t, we define ∑
S
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t where x
1
,
x
2
,
x
u
1
,
x
u
2
,
…
,
x
u
t are the entries in x
_ which correspond to the vertices in S.


### 3.1.3. The Two Main Equations That Generate the Conjugate Eigenpairs

We will use the relationshipA
G
K
q
*
x
_
=
λ
x
_ to determine the two main equations that generate the conjugate eigenpairs as follows:
(7)
∑
S
=
λ
2
x
l
-
q
x
l
,
(8)
λ
∑
S
=
q
-
1
∑
S
+
q
-
1
x
l
⟹
∑
S
=
q
-
1
x
l
λ
-
q
-
1
.
Substitute (8) into (7) to get (
q
-
1
)
λ
x
l
/
λ
-
(
q
-
1
)
=
λ
2
x
l
-
q
x
l, λ
≠
q
-
1, so that
(9)
q
-
1
λ
=
λ
2
λ
-
q
-
1
-
q
λ
-
q
-
1
⟹
λ
3
-
λ
2
(
q
-
1
)
-
q
λ
+
q
(
q
-
1
)
-
λ
(
q
-
1
)
=
0
⟹
(
λ
-
q
)
(
λ
2
+
λ
-
(
q
-
1
)
)
=
0
.
This gives us three eigenvalues, namely, λ
=
q and the conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2.


### 3.1.4. The Caseq
=
4

Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
17
T be an eigenvector of G
K
4
*. Then A
G
K
4
*
x
_
=
λ
x
_ gives
(10)
x
2
+
x
6
+
x
10
+
x
14
x
3
+
x
4
+
x
5
+
x
1
x
2
+
x
4
+
x
5
+
x
17
x
3
+
x
5
+
x
2
+
x
8
x
2
+
x
3
+
x
4
+
x
7
x
1
+
x
7
+
x
8
+
x
9
x
5
+
x
6
+
x
8
+
x
9
x
4
+
x
6
+
x
7
+
x
9
x
6
+
x
7
+
x
8
+
x
11
x
1
+
x
11
+
x
12
+
x
13
x
9
+
x
10
+
x
12
+
x
13
x
10
+
x
11
+
x
13
+
x
16
x
10
+
x
11
+
x
12
+
x
15
x
1
+
x
15
+
x
16
+
x
17
x
13
+
x
14
+
x
16
+
x
17
x
12
+
x
14
+
x
15
+
x
17
x
3
+
x
14
+
x
15
+
x
16
=
λ
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
11
x
12
x
13
x
14
x
15
x
16
x
17
.
Taking the last equation, we get
(11)
x
3
+
x
14
+
x
15
+
x
16
=
λ
x
17
⟹
λ
x
3
+
x
14
+
x
15
+
x
16
=
λ
λ
x
17
⟹
λ
x
3
+
λ
x
14
+
λ
x
15
+
λ
x
16
=
λ
2
x
17
.
Expand the left hand side, using the equations corresponding to the neighbours of v
3, v
14, v
15, and v
16 to get
(12)
(
x
2
+
x
4
+
x
5
+
x
17
)
+
(
x
1
+
x
15
+
x
16
+
x
17
)
+
(
x
13
+
x
14
+
x
16
+
x
17
)
+
(
x
12
+
x
14
+
x
15
+
x
17
)
=
λ
2
x
17
⟹
x
1
+
x
2
+
x
4
+
x
5
+
2
(
x
14
+
x
15
+
x
16
)
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
.
Step 2. Put x
16
=
-
x
15 (second and third to last entries of x
_ have opposite signs and are called the switching pair). Then we have
(13)
x
1
+
x
2
+
x
4
+
x
5
+
2
x
14
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
.
Let T
=
v
1
,
v
2 and let U be the set of all vertices that belong to the second last clique, which are neighbours of the last clique; that is, U
=
v
12
,
v
13. Then the generating set S
=
T
∪
U
=
{
v
1
,
v
2
}
∪
v
12
,
v
13
=
{
v
1
,
v
2
,
v
12
,
v
13
}.Step 3. Set x
4
=
x
5
=
x
14
=
0; then
(14)
x
1
+
x
2
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
⟹
x
1
+
x
2
+
x
12
+
x
13
=
λ
2
x
17
-
4
x
17
⟹
∑
S
=
λ
2
x
17
-
4
x
17
.
This verifies (7) of Section 3.1.2 for the case q
=
4.Step 4. Take the neighbours of the vertices in S
=
v
1
,
v
2
,
v
12
,
v
13 to get
(15)
(
x
2
+
x
6
+
x
10
+
x
14
)
+
(
x
1
+
x
3
+
x
4
+
x
5
)
+
(
x
10
+
x
11
+
x
13
+
x
16
)
+
(
x
10
+
x
11
+
x
12
+
x
15
)
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
.
From above, x
4
=
x
5
=
x
14
=
0, and x
16
=
-
x
15, so that
(16)
x
2
+
x
6
+
x
10
+
x
1
+
x
3
+
x
10
+
x
11
+
x
13
+
x
10
+
x
11
+
x
12
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
x
3
+
x
6
+
3
x
10
+
2
x
11
+
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
.
Now set x
3
=
2
x
1, x
6
=
2
x
13, x
10
=
λ
x
17, x
11
=
x
2, and x
12
=
0. Then
(17)
x
1
+
x
2
+
x
3
+
x
6
+
3
x
10
+
2
x
11
+
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
2
x
1
+
2
x
13
+
3
λ
x
17
+
2
x
2
+
3
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
3
x
1
+
3
x
2
+
3
x
12
+
3
x
13
+
3
λ
x
17
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
3
(
x
1
+
x
2
+
x
12
+
x
13
)
+
3
λ
x
17
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
x
12
+
x
13
=
3
λ
x
17
λ
-
3
⟹
∑
S
=
3
λ
x
17
λ
-
3
.
This verifies (8) of Section 3.1.2 for the case q
=
4.Step 5. Substitute (17) into (14) to get
(18)
3
λ
x
17
λ
-
3
=
λ
2
x
17
-
4
x
17
⟹
λ
2
(
λ
-
3
)
x
17
-
4
(
λ
-
3
)
x
17
=
3
λ
x
17
⟹
λ
3
x
17
-
3
λ
2
x
17
-
4
λ
x
26
+
12
x
17
-
3
λ
x
17
=
0
⟹
λ
3
x
17
-
3
λ
2
x
17
-
7
λ
x
26
+
12
x
17
=
0
⟹
(
λ
-
4
)
(
λ
2
+
λ
-
3
)
x
17
=
0
⟹
λ
=
4
or
λ
=
-
1
±
1
-
4
-
3
2
=
-
1
±
13
2
.
So we have eigenvalues λ
=
4 (which is the same as the degree of the vertices in the 4-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
13
/
2.


### 3.1.5. The Caseq
=
5

Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
26
T be an eigenvector of G
K
5
*. Then the last equation from A
G
K
5
*
x
_
=
λ
x
_ gives
(19)
x
3
+
x
22
+
x
23
+
x
24
+
x
25
=
λ
x
26
⟹
λ
x
3
+
x
22
+
x
23
+
x
24
+
x
25
=
λ
λ
x
26
⟹
λ
x
3
+
λ
x
22
+
λ
x
23
+
λ
x
24
+
λ
x
25
=
λ
2
x
26
.
Expand the left hand side, using the equations corresponding to the neighbours of v
3, v
22, v
23, v
24, and v
25 to get
(20)
x
2
+
x
4
+
x
5
+
x
6
+
x
26
+
x
1
+
x
23
+
x
24
+
x
25
+
x
26
+
x
21
+
x
22
+
x
24
+
x
25
+
x
26
+
x
20
+
x
22
+
x
23
+
x
25
+
x
26
+
x
4
+
x
22
+
x
23
+
x
24
+
x
26
=
λ
2
x
26
⟹
x
1
+
x
2
+
2
x
4
+
x
5
+
x
6
+
x
20
+
x
21
+
3
x
22
+
3
x
23
+
3
x
24
+
3
x
25
+
5
x
26
=
λ
2
x
26
.Step 2. Put x
25
=
-
x
24 (second and third to last entries of x
_ have opposite signs and are called the switching pair). Set T
=
v
1
,
v
2 and U
=
{all vertices in S that belong to the second last clique, which are neighbours of the last clique}
=
v
20
,
v
21. Then the generating set S
=
T
∪
U
=
{
v
1
,
v
2
}
∪
v
20
,
v
21
=
{
v
1
,
v
2
,
v
20
,
v
21
}.Then we havex
1
+
x
2
+
2
x
4
+
x
5
+
x
6
+
x
20
+
x
21
+
3
x
22
+
3
x
23
+
5
x
26
=
λ
2
x
26.Step 3. Put x
4
=
x
5
=
0, x
6
=
-
3
x
22, and x
23
=
0, so we have
(21)
x
1
+
x
2
+
x
20
+
x
21
+
5
x
26
=
λ
2
x
26
⟹
x
1
+
x
2
+
x
20
+
x
21
=
λ
2
x
26
-
5
x
26
⟹
∑
S
=
λ
2
x
26
-
5
x
26
.
This verifies (7) of Section 3.1.2 for the case q
=
5.Step 4. Take the neighbours of the vertices in S
=
v
1
,
v
2
,
v
20
,
v
21 to get
(22)
x
2
+
x
7
+
x
12
+
x
17
+
x
22
+
x
1
+
x
3
+
x
4
+
x
5
+
x
6
+
x
17
+
x
18
+
x
19
+
x
21
+
x
24
+
x
17
+
x
18
+
x
19
+
x
20
+
x
23
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
From above, x
4
=
x
5
=
0, x
6
=
-
3
x
22, x
23
=
0, and x
25
=
-
x
24 so that
(23)
x
2
+
x
7
+
x
12
+
x
17
+
x
22
+
x
1
+
x
3
-
3
x
22
+
x
17
+
x
18
+
x
19
+
x
21
+
x
24
+
x
17
+
x
18
+
x
19
+
x
20
=
λ
x
1
+
x
2
+
x
20
+
x
21
⟹
x
1
+
x
2
+
x
3
+
x
7
+
x
12
+
3
x
17
+
3
x
18
+
2
x
19
+
x
20
+
x
21
-
2
x
22
+
x
24
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
Now set x
3
=
3
x
2, x
7
=
3
x
1, x
12
=
4
λ
x
26, x
17
=
0, x
18
=
3
/
2
x
20, x
19
=
3
/
2
x
21, and x
24
=
2
x
22. Then
(24)
x
1
+
x
2
+
x
3
+
x
7
+
x
12
+
3
x
17
+
2
x
18
+
2
x
19
+
x
20
+
x
21
-
2
x
22
+
x
24
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
⟹
x
1
+
x
2
+
3
x
2
+
3
x
1
+
4
λ
x
26
+
3
x
20
+
3
x
21
+
x
20
+
x
21
-
2
x
22
+
2
x
22
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
⟹
4
x
1
+
4
x
2
+
4
x
20
+
4
x
21
+
4
λ
x
26
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
⟹
x
1
+
x
2
+
x
20
+
x
21
=
4
x
26
λ
-
4
⟹
∑
S
=
4
x
26
λ
-
4
.
This verifies (8) of Section 3.1.2 for the case q
=
5.Step 5. Substitute (24) into (21) to get
(25)
4
λ
x
26
λ
-
4
=
λ
2
x
26
-
5
x
26
⟹
λ
2
(
λ
-
4
)
x
26
-
5
(
λ
-
4
)
x
26
=
4
λ
x
26
⟹
λ
3
x
26
-
4
λ
2
x
26
-
5
λ
x
26
+
20
x
26
-
4
λ
x
26
=
0
⟹
λ
3
x
26
-
4
λ
2
x
26
-
9
λ
x
26
+
20
x
26
=
0
⟹
(
λ
-
5
)
(
λ
2
+
λ
-
4
)
x
26
=
0
⟹
λ
=
5
or
λ
=
-
1
±
1
-
4
-
4
2
=
-
1
±
17
2
.
So we have eigenvalues λ
=
5 (which is the same as the degree of the vertices in the 5-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
17
/
2.


### 3.1.6. Eigenvalues of General Case

Refer to Section3.1.1 for the vertex notation and definitions. We require the following additional definitions to clarify the proof for the general case, where q
≥
6.(1)
λ
x
l is equal to the sum of the entries in x
_ whose corresponding vertices are adjacent to v
l in G
K
q
*; that is, λ
x
l
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1 as v
l is adjacent to the set of vertices v
3
,
v
a
,
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
,
v
l
-
21
,
v
l
-
1 in G
K
q
*.
(2)
Let the neighbours ofv
l be N
v
l
=
v
l
1
,
v
l
2
,
…
,
v
l
q
=
v
3
,
v
a
,
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
,
v
l
-
2
,
v
l
-
1. Then, as per (7) above, λ
x
l is equal to the sum of the entries in x
_ whose corresponding vertices are in N
v
l; that is, λ
x
l
=
x
l
1
+
x
l
2
+
⋯
+
x
l
q
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1.
(3)
LetN
N
v
l be the set of vertices which are adjacent to the vertices in N
v
l in G
K
q
*. Then λ
λ
x
l is the sum of the entries in x
_ whose corresponding vertices are in N
N
v
l.
(4)
LetQ be the set of vertices {
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
} which all belong to the last clique. Set x
k
=
0 for all v
k
∈
Q. Note that v
l
-
2
,
v
l
-
1
,
v
l
∉
Q.
(5)
The set of neighbours ofv
a is v
1
,
v
l
-
2
,
v
l
-
1
,
v
l, together with the set of vertices in Q.
(6)
Lett
=
q
-
1
/
2
;
q
odd
q
/
2
;
q
even
. and let R be the set of vertices from N
N
v
l which belong to the first clique, which are neighbours of vertices in the last clique. Then R
=
v
r
1
,
v
r
2
,
…
,
v
r
q
-
2
-
t
=
v
4
,
v
6
,
v
8
,
…
,
v
q
-
1.
(7)
LetU be the set of vertices from N
N
v
l which belong to the second last q
-
1th clique, which are neighbours of the vertices from the last qth clique. Then U
=
v
u
1
,
v
u
2
,
…
,
v
u
t.
(8)
LetT
=
{
v
1
,
v
2
}.
(9)
LetS be the generating set of vertices; then S
=
T
∪
U, and ∑
S
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t.
(10)
LetP be the set of vertices in the second last clique, excluding the anchor vertex, which are not neighbours of the last clique and are therefore not in U as defined above. Then P
=
v
p
1
,
v
p
2
,
…
,
v
p
q
-
1
-
t.
(11)
LetW be the subset of vertices in the last clique, whose vertices join backwards to vertices of U. Then W
=
v
w
1
,
v
w
2
,
…
,
v
w
t
=
v
a
+
1
,
v
a
+
2
,
v
a
+
4
,
…
,
v
a
+
q
-
3
=
v
l
-
2.Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T be an eigenvector of G
K
q
*. Then the last equation of A
G
K
q
*
x
_
=
λ
x
_ gives
(26)
λ
x
l
=
x
l
1
+
x
2
+
⋯
+
x
l
q
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1
.
So,
(27)
λ
2
x
l
=
λ
λ
x
l
=
λ
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1
=
λ
x
3
+
λ
x
a
+
λ
x
a
+
1
+
λ
x
a
+
2
+
⋯
+
λ
x
l
-
3
+
λ
x
l
-
2
+
λ
x
l
-
1
=
x
1
+
x
2
+
x
4
+
x
5
+
⋯
+
x
q
+
x
q
+
1
+
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
1
,
(
q
-
2
)
x
a
+
2
+
⋯
+
(
q
-
2
)
x
a
+
t
+
⋯
+
(
q
-
2
)
x
l
-
3
+
(
q
-
2
)
x
l
-
2
+
(
q
-
2
)
x
l
-
1
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
x
r
1
+
x
r
2
+
⋯
+
x
r
q
-
2
-
t
.Step 2. Set x
l
-
1
=
-
x
l
-
2 (switching entries).Step 3. Set x
4
=
x
5
=
⋯
=
x
q
=
0. This implies x
r
1
=
x
r
2
=
⋯
=
x
r
q
-
2
-
t
=
0. Set x
k
=
0 for all v
k
∈
Q, and set x
q
+
1
=
-
(
q
-
2
)
x
a. Then
(28)
λ
2
x
l
=
x
1
+
x
2
+
x
4
+
x
5
+
⋯
+
x
q
+
x
q
+
1
+
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
1
,
(
q
-
2
)
x
a
+
2
+
⋯
+
(
q
-
2
)
x
a
+
t
+
⋯
+
(
q
-
2
)
x
l
-
3
+
(
q
-
2
)
x
l
-
2
+
(
q
-
2
)
x
l
-
1
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
x
r
1
+
x
r
2
+
⋯
+
x
r
q
-
2
-
t
=
x
1
+
x
2
+
0
+
0
+
⋯
+
0
-
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
0
+
0
+
⋯
+
0
+
0
+
(
q
-
2
)
x
l
-
2
-
(
q
-
2
)
x
l
-
2
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
(
0
+
0
+
⋯
+
0
)
⟹
λ
2
x
l
=
x
1
+
x
2
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
⟹
λ
2
x
l
-
q
x
l
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
⟹
λ
2
x
l
-
q
x
l
=
∑
S
⟹
∑
S
=
λ
2
x
l
-
q
x
l
.
This verifies (7) of Section 3.1.2 for the general case q.Step 4. Now take the neighbours of the generating set S, where
(29)
S
=
T
∪
U
=
v
1
,
v
2
∪
v
u
1
,
v
u
2
,
…
,
v
u
t
,
where t
=
q
-
1
/
2, if q is odd, and t
=
q
/
2, if q is even.The neighbours ofv
1 are N
v
1
=
v
2
,
v
2
+
q
,
v
2
+
2
q
,
…
,
v
2
+
q
(
q
-
1
). The set of neighbours of v
2 are N
v
2
=
v
1
,
v
3
,
v
4
,
…
,
v
q
+
1. The sum of the entries in x
_ corresponding to the neighbours of the vertices in U is ∑
N
v
u
1
,
v
u
2
,
…
,
v
u
q
-
1
-
t
=
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
∑
W.Then the sum of the entries inx
_ corresponding to the neighbours of the vertices in S is
(30)
λ
∑
S
=
∑
N
S
=
∑
N
v
1
+
∑
N
v
1
+
∑
N
v
u
1
,
v
u
1
,
…
,
v
u
q
-
1
-
t
=
(
x
2
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
)
+
(
x
1
+
x
3
+
x
4
+
⋯
+
x
q
+
x
q
+
1
)
+
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
∑
W
.
As before, set x
l
-
1
=
-
x
l
-
2 and set x
4
=
x
5
=
⋯
=
x
q
=
0. This implies x
r
1
=
x
r
2
=
⋯
=
x
r
q
-
2
-
t
=
0.Setx
k
=
0 for all v
k
∈
Q, and set x
q
+
1
=
-
(
q
-
2
)
x
a. Then,
(31)
λ
∑
S
=
(
x
2
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
)
+
(
x
1
+
x
3
+
0
+
⋯
+
0
-
(
q
-
2
)
x
a
)
+
t
-
1
∑
U
+
t
x
a
-
q
+
t
∑
P
+
0
+
0
+
⋯
+
0
+
x
l
-
2
=
x
1
+
x
2
+
x
3
-
(
q
-
2
)
x
a
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
+
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
x
l
-
2
.
Now set x
3
=
q
-
2
x
2, x
2
+
q
=
q
-
2
x
1, x
2
+
2
q
=
q
-
1
λ
x
l, x
2
+
3
q
=
x
2
+
4
q
=
⋯
=
x
2
+
q
-
2
q
=
0, x
2
+
q
-
1
q
=
x
a, x
a
-
q
=
x
2
+
q
q
-
2
=
0, and x
l
-
2
=
(
q
-
3
)
x
a
=
-
x
l
-
1. Then
(32)
λ
∑
S
=
x
1
+
x
2
+
(
q
-
2
)
x
2
-
(
q
-
2
)
x
a
+
(
q
-
2
)
x
1
+
(
q
-
1
)
λ
x
l
+
0
+
⋯
+
0
+
x
a
+
(
t
-
1
)
∑
U
+
t
0
+
t
∑
P
+
(
q
-
3
)
x
a
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
∑
U
+
t
∑
P
.
Set x
p
1
=
q
-
t
/
t
x
u
1, x
p
2
=
q
-
t
/
t
x
,
…
,
x
p
t
=
q
-
t
/
t
x
u
t, and x
p
(
t
+
1
)
=
0 if q is even, as P has one more vertex than U when q is even. Then,
(33)
λ
∑
S
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
∑
U
+
t
∑
P
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
(
x
k
1
+
x
k
2
+
+
⋯
+
x
k
t
)
+
t
q
-
t
t
(
x
k
1
+
x
k
2
+
⋯
+
x
k
t
)
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
q
-
1
)
(
x
k
1
+
x
k
2
+
+
⋯
+
x
k
t
)
=
(
q
-
1
)
(
x
1
+
x
2
+
x
k
1
+
x
k
2
+
⋯
+
x
k
t
)
+
(
q
-
1
)
λ
x
l
=
(
q
-
1
)
∑
S
+
(
q
-
1
)
λ
x
l
⟹
λ
-
q
-
1
∑
S
=
q
-
1
λ
x
l
⟹
∑
S
=
q
-
1
λ
x
l
λ
-
q
-
1
.
Substituting (33) into (28), we get
(34)
q
-
1
λ
x
l
λ
-
(
q
-
1
)
=
λ
2
x
l
-
q
x
l
⟹
λ
2
(
λ
-
(
q
-
1
)
)
x
l
-
q
(
λ
-
(
q
-
1
)
)
x
l
=
(
q
-
1
)
λ
x
l
⟹
λ
3
x
l
-
(
q
-
1
)
λ
2
x
l
-
q
λ
x
l
+
q
(
q
-
1
)
x
l
-
(
q
-
1
)
λ
x
l
=
0
⟹
λ
3
x
l
-
(
q
-
1
)
λ
2
x
l
-
(
2
q
-
1
)
λ
x
l
+
q
(
q
-
1
)
x
l
=
0
⟹
(
λ
-
q
)
(
λ
2
+
λ
-
(
q
-
1
)
)
x
l
=
0
⟹
λ
=
q
or
λ
=
-
1
±
1
-
(
-
4
(
q
-
1
)
)
2
=
-
1
±
1
+
4
(
q
-
1
)
2
.
So we have eigenvalues λ
=
q (which is the same as the degree of the vertices in the q-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2. This completes the proof of Theorem 1.This concludes the proof of the conjugate eigenpair of the adjacency matrix associated with theq-cliqued graphs, as constructed in Section 2. It is interesting to note that the conjugate eigenpair is a function of the clique number of the graph. It can also be proved that q-cliqued graphs are design graphs—see Jessop [5].In the next section, we determine the eigen-bi-balanced properties ofq-cliqued graphs associated with the conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2.


## 3.1.1. Notation Convention

(1)
LetA
G
K
q
* be the adjacency matrix of the q-cliqued graph G
K
q
*. Let x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T be an eigenvector of A
G
K
q
*, corresponding to the eigenvalue λ. Then A
G
K
q
*
x
_
=
λ
x
_.
(2)
Ifx
i is the ith entry in x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1, then we say that x
i corresponds to the ith vertex v
i in G
K
q
* and vice versa.
(3)
The first entry inx
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T is x
1, the second entry is x
2, and the third entry is x
3.
(4)
The set of vertices in the first cliqueK
q
1 is v
2
,
v
3
,
…
,
v
q
,
v
q
+
1 and the corresponding set of entries in x
_ is x
2
,
x
3
,
…
,
x
q
,
x
q
+
1.
(5)
The anchor vertex of each clique is the vertex in each clique which is joined to the first vertexv
1. The anchor vertex of the last clique is v
a
=
v
2
+
q
(
q
-
1
), and the anchor vertex of the second to last clique is v
a
-
q
=
v
2
+
q
(
q
-
2
).
(6)
The switching pair of entries inx
_ is x
q
2
-
1
=
x
l
-
2 (third last entry in x
_) and x
q
2
=
x
l
-
1 (second last entry in x
_).
(7)
The last entry inx
_ is x
l
=
x
q
2
+
1.


## 3.1.2. The Generating Set

LetT
=
{
v
1
,
v
2
} and let U be the set of vertices of the second last clique which are adjacent to vertices in the last clique, that is, U
=
v
u
1
,
v
u
2
,
…
,
v
u
t, where t
=
q
-
1
/
2, when q is odd, or t
=
q
/
2, when q is even. Let S
=
T
∪
U be the generating set of vertices. Then, if S
=
v
1
,
v
2
,
v
u
1
,
v
u
2
,
…
,
v
u
t, we define ∑
S
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t where x
1
,
x
2
,
x
u
1
,
x
u
2
,
…
,
x
u
t are the entries in x
_ which correspond to the vertices in S.


## 3.1.3. The Two Main Equations That Generate the Conjugate Eigenpairs

We will use the relationshipA
G
K
q
*
x
_
=
λ
x
_ to determine the two main equations that generate the conjugate eigenpairs as follows:
(7)
∑
S
=
λ
2
x
l
-
q
x
l
,
(8)
λ
∑
S
=
q
-
1
∑
S
+
q
-
1
x
l
⟹
∑
S
=
q
-
1
x
l
λ
-
q
-
1
.
Substitute (8) into (7) to get (
q
-
1
)
λ
x
l
/
λ
-
(
q
-
1
)
=
λ
2
x
l
-
q
x
l, λ
≠
q
-
1, so that
(9)
q
-
1
λ
=
λ
2
λ
-
q
-
1
-
q
λ
-
q
-
1
⟹
λ
3
-
λ
2
(
q
-
1
)
-
q
λ
+
q
(
q
-
1
)
-
λ
(
q
-
1
)
=
0
⟹
(
λ
-
q
)
(
λ
2
+
λ
-
(
q
-
1
)
)
=
0
.
This gives us three eigenvalues, namely, λ
=
q and the conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2.


## 3.1.4. The Caseq
=
4

Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
17
T be an eigenvector of G
K
4
*. Then A
G
K
4
*
x
_
=
λ
x
_ gives
(10)
x
2
+
x
6
+
x
10
+
x
14
x
3
+
x
4
+
x
5
+
x
1
x
2
+
x
4
+
x
5
+
x
17
x
3
+
x
5
+
x
2
+
x
8
x
2
+
x
3
+
x
4
+
x
7
x
1
+
x
7
+
x
8
+
x
9
x
5
+
x
6
+
x
8
+
x
9
x
4
+
x
6
+
x
7
+
x
9
x
6
+
x
7
+
x
8
+
x
11
x
1
+
x
11
+
x
12
+
x
13
x
9
+
x
10
+
x
12
+
x
13
x
10
+
x
11
+
x
13
+
x
16
x
10
+
x
11
+
x
12
+
x
15
x
1
+
x
15
+
x
16
+
x
17
x
13
+
x
14
+
x
16
+
x
17
x
12
+
x
14
+
x
15
+
x
17
x
3
+
x
14
+
x
15
+
x
16
=
λ
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
11
x
12
x
13
x
14
x
15
x
16
x
17
.
Taking the last equation, we get
(11)
x
3
+
x
14
+
x
15
+
x
16
=
λ
x
17
⟹
λ
x
3
+
x
14
+
x
15
+
x
16
=
λ
λ
x
17
⟹
λ
x
3
+
λ
x
14
+
λ
x
15
+
λ
x
16
=
λ
2
x
17
.
Expand the left hand side, using the equations corresponding to the neighbours of v
3, v
14, v
15, and v
16 to get
(12)
(
x
2
+
x
4
+
x
5
+
x
17
)
+
(
x
1
+
x
15
+
x
16
+
x
17
)
+
(
x
13
+
x
14
+
x
16
+
x
17
)
+
(
x
12
+
x
14
+
x
15
+
x
17
)
=
λ
2
x
17
⟹
x
1
+
x
2
+
x
4
+
x
5
+
2
(
x
14
+
x
15
+
x
16
)
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
.
Step 2. Put x
16
=
-
x
15 (second and third to last entries of x
_ have opposite signs and are called the switching pair). Then we have
(13)
x
1
+
x
2
+
x
4
+
x
5
+
2
x
14
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
.
Let T
=
v
1
,
v
2 and let U be the set of all vertices that belong to the second last clique, which are neighbours of the last clique; that is, U
=
v
12
,
v
13. Then the generating set S
=
T
∪
U
=
{
v
1
,
v
2
}
∪
v
12
,
v
13
=
{
v
1
,
v
2
,
v
12
,
v
13
}.Step 3. Set x
4
=
x
5
=
x
14
=
0; then
(14)
x
1
+
x
2
+
x
12
+
x
13
+
4
x
17
=
λ
2
x
17
⟹
x
1
+
x
2
+
x
12
+
x
13
=
λ
2
x
17
-
4
x
17
⟹
∑
S
=
λ
2
x
17
-
4
x
17
.
This verifies (7) of Section 3.1.2 for the case q
=
4.Step 4. Take the neighbours of the vertices in S
=
v
1
,
v
2
,
v
12
,
v
13 to get
(15)
(
x
2
+
x
6
+
x
10
+
x
14
)
+
(
x
1
+
x
3
+
x
4
+
x
5
)
+
(
x
10
+
x
11
+
x
13
+
x
16
)
+
(
x
10
+
x
11
+
x
12
+
x
15
)
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
.
From above, x
4
=
x
5
=
x
14
=
0, and x
16
=
-
x
15, so that
(16)
x
2
+
x
6
+
x
10
+
x
1
+
x
3
+
x
10
+
x
11
+
x
13
+
x
10
+
x
11
+
x
12
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
x
3
+
x
6
+
3
x
10
+
2
x
11
+
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
.
Now set x
3
=
2
x
1, x
6
=
2
x
13, x
10
=
λ
x
17, x
11
=
x
2, and x
12
=
0. Then
(17)
x
1
+
x
2
+
x
3
+
x
6
+
3
x
10
+
2
x
11
+
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
2
x
1
+
2
x
13
+
3
λ
x
17
+
2
x
2
+
3
x
12
+
x
13
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
3
x
1
+
3
x
2
+
3
x
12
+
3
x
13
+
3
λ
x
17
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
3
(
x
1
+
x
2
+
x
12
+
x
13
)
+
3
λ
x
17
=
λ
(
x
1
+
x
2
+
x
12
+
x
13
)
⟹
x
1
+
x
2
+
x
12
+
x
13
=
3
λ
x
17
λ
-
3
⟹
∑
S
=
3
λ
x
17
λ
-
3
.
This verifies (8) of Section 3.1.2 for the case q
=
4.Step 5. Substitute (17) into (14) to get
(18)
3
λ
x
17
λ
-
3
=
λ
2
x
17
-
4
x
17
⟹
λ
2
(
λ
-
3
)
x
17
-
4
(
λ
-
3
)
x
17
=
3
λ
x
17
⟹
λ
3
x
17
-
3
λ
2
x
17
-
4
λ
x
26
+
12
x
17
-
3
λ
x
17
=
0
⟹
λ
3
x
17
-
3
λ
2
x
17
-
7
λ
x
26
+
12
x
17
=
0
⟹
(
λ
-
4
)
(
λ
2
+
λ
-
3
)
x
17
=
0
⟹
λ
=
4
or
λ
=
-
1
±
1
-
4
-
3
2
=
-
1
±
13
2
.
So we have eigenvalues λ
=
4 (which is the same as the degree of the vertices in the 4-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
13
/
2.


## 3.1.5. The Caseq
=
5

Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
26
T be an eigenvector of G
K
5
*. Then the last equation from A
G
K
5
*
x
_
=
λ
x
_ gives
(19)
x
3
+
x
22
+
x
23
+
x
24
+
x
25
=
λ
x
26
⟹
λ
x
3
+
x
22
+
x
23
+
x
24
+
x
25
=
λ
λ
x
26
⟹
λ
x
3
+
λ
x
22
+
λ
x
23
+
λ
x
24
+
λ
x
25
=
λ
2
x
26
.
Expand the left hand side, using the equations corresponding to the neighbours of v
3, v
22, v
23, v
24, and v
25 to get
(20)
x
2
+
x
4
+
x
5
+
x
6
+
x
26
+
x
1
+
x
23
+
x
24
+
x
25
+
x
26
+
x
21
+
x
22
+
x
24
+
x
25
+
x
26
+
x
20
+
x
22
+
x
23
+
x
25
+
x
26
+
x
4
+
x
22
+
x
23
+
x
24
+
x
26
=
λ
2
x
26
⟹
x
1
+
x
2
+
2
x
4
+
x
5
+
x
6
+
x
20
+
x
21
+
3
x
22
+
3
x
23
+
3
x
24
+
3
x
25
+
5
x
26
=
λ
2
x
26
.Step 2. Put x
25
=
-
x
24 (second and third to last entries of x
_ have opposite signs and are called the switching pair). Set T
=
v
1
,
v
2 and U
=
{all vertices in S that belong to the second last clique, which are neighbours of the last clique}
=
v
20
,
v
21. Then the generating set S
=
T
∪
U
=
{
v
1
,
v
2
}
∪
v
20
,
v
21
=
{
v
1
,
v
2
,
v
20
,
v
21
}.Then we havex
1
+
x
2
+
2
x
4
+
x
5
+
x
6
+
x
20
+
x
21
+
3
x
22
+
3
x
23
+
5
x
26
=
λ
2
x
26.Step 3. Put x
4
=
x
5
=
0, x
6
=
-
3
x
22, and x
23
=
0, so we have
(21)
x
1
+
x
2
+
x
20
+
x
21
+
5
x
26
=
λ
2
x
26
⟹
x
1
+
x
2
+
x
20
+
x
21
=
λ
2
x
26
-
5
x
26
⟹
∑
S
=
λ
2
x
26
-
5
x
26
.
This verifies (7) of Section 3.1.2 for the case q
=
5.Step 4. Take the neighbours of the vertices in S
=
v
1
,
v
2
,
v
20
,
v
21 to get
(22)
x
2
+
x
7
+
x
12
+
x
17
+
x
22
+
x
1
+
x
3
+
x
4
+
x
5
+
x
6
+
x
17
+
x
18
+
x
19
+
x
21
+
x
24
+
x
17
+
x
18
+
x
19
+
x
20
+
x
23
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
From above, x
4
=
x
5
=
0, x
6
=
-
3
x
22, x
23
=
0, and x
25
=
-
x
24 so that
(23)
x
2
+
x
7
+
x
12
+
x
17
+
x
22
+
x
1
+
x
3
-
3
x
22
+
x
17
+
x
18
+
x
19
+
x
21
+
x
24
+
x
17
+
x
18
+
x
19
+
x
20
=
λ
x
1
+
x
2
+
x
20
+
x
21
⟹
x
1
+
x
2
+
x
3
+
x
7
+
x
12
+
3
x
17
+
3
x
18
+
2
x
19
+
x
20
+
x
21
-
2
x
22
+
x
24
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
Now set x
3
=
3
x
2, x
7
=
3
x
1, x
12
=
4
λ
x
26, x
17
=
0, x
18
=
3
/
2
x
20, x
19
=
3
/
2
x
21, and x
24
=
2
x
22. Then
(24)
x
1
+
x
2
+
x
3
+
x
7
+
x
12
+
3
x
17
+
2
x
18
+
2
x
19
+
x
20
+
x
21
-
2
x
22
+
x
24
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
⟹
x
1
+
x
2
+
3
x
2
+
3
x
1
+
4
λ
x
26
+
3
x
20
+
3
x
21
+
x
20
+
x
21
-
2
x
22
+
2
x
22
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
⟹
4
x
1
+
4
x
2
+
4
x
20
+
4
x
21
+
4
λ
x
26
=
λ
(
x
1
+
x
2
+
x
20
+
x
21
)
.
⟹
x
1
+
x
2
+
x
20
+
x
21
=
4
x
26
λ
-
4
⟹
∑
S
=
4
x
26
λ
-
4
.
This verifies (8) of Section 3.1.2 for the case q
=
5.Step 5. Substitute (24) into (21) to get
(25)
4
λ
x
26
λ
-
4
=
λ
2
x
26
-
5
x
26
⟹
λ
2
(
λ
-
4
)
x
26
-
5
(
λ
-
4
)
x
26
=
4
λ
x
26
⟹
λ
3
x
26
-
4
λ
2
x
26
-
5
λ
x
26
+
20
x
26
-
4
λ
x
26
=
0
⟹
λ
3
x
26
-
4
λ
2
x
26
-
9
λ
x
26
+
20
x
26
=
0
⟹
(
λ
-
5
)
(
λ
2
+
λ
-
4
)
x
26
=
0
⟹
λ
=
5
or
λ
=
-
1
±
1
-
4
-
4
2
=
-
1
±
17
2
.
So we have eigenvalues λ
=
5 (which is the same as the degree of the vertices in the 5-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
17
/
2.


## 3.1.6. Eigenvalues of General Case

Refer to Section3.1.1 for the vertex notation and definitions. We require the following additional definitions to clarify the proof for the general case, where q
≥
6.(1)
λ
x
l is equal to the sum of the entries in x
_ whose corresponding vertices are adjacent to v
l in G
K
q
*; that is, λ
x
l
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1 as v
l is adjacent to the set of vertices v
3
,
v
a
,
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
,
v
l
-
21
,
v
l
-
1 in G
K
q
*.
(2)
Let the neighbours ofv
l be N
v
l
=
v
l
1
,
v
l
2
,
…
,
v
l
q
=
v
3
,
v
a
,
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
,
v
l
-
2
,
v
l
-
1. Then, as per (7) above, λ
x
l is equal to the sum of the entries in x
_ whose corresponding vertices are in N
v
l; that is, λ
x
l
=
x
l
1
+
x
l
2
+
⋯
+
x
l
q
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1.
(3)
LetN
N
v
l be the set of vertices which are adjacent to the vertices in N
v
l in G
K
q
*. Then λ
λ
x
l is the sum of the entries in x
_ whose corresponding vertices are in N
N
v
l.
(4)
LetQ be the set of vertices {
v
a
+
1
,
v
a
+
2
,
…
,
v
l
-
3
} which all belong to the last clique. Set x
k
=
0 for all v
k
∈
Q. Note that v
l
-
2
,
v
l
-
1
,
v
l
∉
Q.
(5)
The set of neighbours ofv
a is v
1
,
v
l
-
2
,
v
l
-
1
,
v
l, together with the set of vertices in Q.
(6)
Lett
=
q
-
1
/
2
;
q
odd
q
/
2
;
q
even
. and let R be the set of vertices from N
N
v
l which belong to the first clique, which are neighbours of vertices in the last clique. Then R
=
v
r
1
,
v
r
2
,
…
,
v
r
q
-
2
-
t
=
v
4
,
v
6
,
v
8
,
…
,
v
q
-
1.
(7)
LetU be the set of vertices from N
N
v
l which belong to the second last q
-
1th clique, which are neighbours of the vertices from the last qth clique. Then U
=
v
u
1
,
v
u
2
,
…
,
v
u
t.
(8)
LetT
=
{
v
1
,
v
2
}.
(9)
LetS be the generating set of vertices; then S
=
T
∪
U, and ∑
S
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t.
(10)
LetP be the set of vertices in the second last clique, excluding the anchor vertex, which are not neighbours of the last clique and are therefore not in U as defined above. Then P
=
v
p
1
,
v
p
2
,
…
,
v
p
q
-
1
-
t.
(11)
LetW be the subset of vertices in the last clique, whose vertices join backwards to vertices of U. Then W
=
v
w
1
,
v
w
2
,
…
,
v
w
t
=
v
a
+
1
,
v
a
+
2
,
v
a
+
4
,
…
,
v
a
+
q
-
3
=
v
l
-
2.Step 1. Let x
_
=
x
1
,
x
2
,
…
,
x
q
2
+
1
T be an eigenvector of G
K
q
*. Then the last equation of A
G
K
q
*
x
_
=
λ
x
_ gives
(26)
λ
x
l
=
x
l
1
+
x
2
+
⋯
+
x
l
q
=
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1
.
So,
(27)
λ
2
x
l
=
λ
λ
x
l
=
λ
x
3
+
x
a
+
x
a
+
1
+
x
a
+
2
+
⋯
+
x
l
-
3
+
x
l
-
2
+
x
l
-
1
=
λ
x
3
+
λ
x
a
+
λ
x
a
+
1
+
λ
x
a
+
2
+
⋯
+
λ
x
l
-
3
+
λ
x
l
-
2
+
λ
x
l
-
1
=
x
1
+
x
2
+
x
4
+
x
5
+
⋯
+
x
q
+
x
q
+
1
+
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
1
,
(
q
-
2
)
x
a
+
2
+
⋯
+
(
q
-
2
)
x
a
+
t
+
⋯
+
(
q
-
2
)
x
l
-
3
+
(
q
-
2
)
x
l
-
2
+
(
q
-
2
)
x
l
-
1
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
x
r
1
+
x
r
2
+
⋯
+
x
r
q
-
2
-
t
.Step 2. Set x
l
-
1
=
-
x
l
-
2 (switching entries).Step 3. Set x
4
=
x
5
=
⋯
=
x
q
=
0. This implies x
r
1
=
x
r
2
=
⋯
=
x
r
q
-
2
-
t
=
0. Set x
k
=
0 for all v
k
∈
Q, and set x
q
+
1
=
-
(
q
-
2
)
x
a. Then
(28)
λ
2
x
l
=
x
1
+
x
2
+
x
4
+
x
5
+
⋯
+
x
q
+
x
q
+
1
+
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
1
,
(
q
-
2
)
x
a
+
2
+
⋯
+
(
q
-
2
)
x
a
+
t
+
⋯
+
(
q
-
2
)
x
l
-
3
+
(
q
-
2
)
x
l
-
2
+
(
q
-
2
)
x
l
-
1
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
x
r
1
+
x
r
2
+
⋯
+
x
r
q
-
2
-
t
=
x
1
+
x
2
+
0
+
0
+
⋯
+
0
-
(
q
-
2
)
x
a
+
(
q
-
2
)
x
a
+
0
+
0
+
⋯
+
0
+
0
+
(
q
-
2
)
x
l
-
2
-
(
q
-
2
)
x
l
-
2
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
+
(
0
+
0
+
⋯
+
0
)
⟹
λ
2
x
l
=
x
1
+
x
2
+
q
x
l
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
⟹
λ
2
x
l
-
q
x
l
=
x
1
+
x
2
+
x
u
1
+
x
u
2
+
⋯
+
x
u
t
⟹
λ
2
x
l
-
q
x
l
=
∑
S
⟹
∑
S
=
λ
2
x
l
-
q
x
l
.
This verifies (7) of Section 3.1.2 for the general case q.Step 4. Now take the neighbours of the generating set S, where
(29)
S
=
T
∪
U
=
v
1
,
v
2
∪
v
u
1
,
v
u
2
,
…
,
v
u
t
,
where t
=
q
-
1
/
2, if q is odd, and t
=
q
/
2, if q is even.The neighbours ofv
1 are N
v
1
=
v
2
,
v
2
+
q
,
v
2
+
2
q
,
…
,
v
2
+
q
(
q
-
1
). The set of neighbours of v
2 are N
v
2
=
v
1
,
v
3
,
v
4
,
…
,
v
q
+
1. The sum of the entries in x
_ corresponding to the neighbours of the vertices in U is ∑
N
v
u
1
,
v
u
2
,
…
,
v
u
q
-
1
-
t
=
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
∑
W.Then the sum of the entries inx
_ corresponding to the neighbours of the vertices in S is
(30)
λ
∑
S
=
∑
N
S
=
∑
N
v
1
+
∑
N
v
1
+
∑
N
v
u
1
,
v
u
1
,
…
,
v
u
q
-
1
-
t
=
(
x
2
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
)
+
(
x
1
+
x
3
+
x
4
+
⋯
+
x
q
+
x
q
+
1
)
+
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
∑
W
.
As before, set x
l
-
1
=
-
x
l
-
2 and set x
4
=
x
5
=
⋯
=
x
q
=
0. This implies x
r
1
=
x
r
2
=
⋯
=
x
r
q
-
2
-
t
=
0.Setx
k
=
0 for all v
k
∈
Q, and set x
q
+
1
=
-
(
q
-
2
)
x
a. Then,
(31)
λ
∑
S
=
(
x
2
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
)
+
(
x
1
+
x
3
+
0
+
⋯
+
0
-
(
q
-
2
)
x
a
)
+
t
-
1
∑
U
+
t
x
a
-
q
+
t
∑
P
+
0
+
0
+
⋯
+
0
+
x
l
-
2
=
x
1
+
x
2
+
x
3
-
(
q
-
2
)
x
a
+
x
2
+
q
+
x
2
+
2
q
+
⋯
+
x
2
+
q
(
q
-
1
)
+
(
t
-
1
)
∑
U
+
t
x
a
-
q
+
t
∑
P
+
x
l
-
2
.
Now set x
3
=
q
-
2
x
2, x
2
+
q
=
q
-
2
x
1, x
2
+
2
q
=
q
-
1
λ
x
l, x
2
+
3
q
=
x
2
+
4
q
=
⋯
=
x
2
+
q
-
2
q
=
0, x
2
+
q
-
1
q
=
x
a, x
a
-
q
=
x
2
+
q
q
-
2
=
0, and x
l
-
2
=
(
q
-
3
)
x
a
=
-
x
l
-
1. Then
(32)
λ
∑
S
=
x
1
+
x
2
+
(
q
-
2
)
x
2
-
(
q
-
2
)
x
a
+
(
q
-
2
)
x
1
+
(
q
-
1
)
λ
x
l
+
0
+
⋯
+
0
+
x
a
+
(
t
-
1
)
∑
U
+
t
0
+
t
∑
P
+
(
q
-
3
)
x
a
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
∑
U
+
t
∑
P
.
Set x
p
1
=
q
-
t
/
t
x
u
1, x
p
2
=
q
-
t
/
t
x
,
…
,
x
p
t
=
q
-
t
/
t
x
u
t, and x
p
(
t
+
1
)
=
0 if q is even, as P has one more vertex than U when q is even. Then,
(33)
λ
∑
S
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
∑
U
+
t
∑
P
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
t
-
1
)
(
x
k
1
+
x
k
2
+
+
⋯
+
x
k
t
)
+
t
q
-
t
t
(
x
k
1
+
x
k
2
+
⋯
+
x
k
t
)
=
(
q
-
1
)
x
1
+
(
q
-
1
)
x
2
+
(
q
-
1
)
λ
x
l
+
(
q
-
1
)
(
x
k
1
+
x
k
2
+
+
⋯
+
x
k
t
)
=
(
q
-
1
)
(
x
1
+
x
2
+
x
k
1
+
x
k
2
+
⋯
+
x
k
t
)
+
(
q
-
1
)
λ
x
l
=
(
q
-
1
)
∑
S
+
(
q
-
1
)
λ
x
l
⟹
λ
-
q
-
1
∑
S
=
q
-
1
λ
x
l
⟹
∑
S
=
q
-
1
λ
x
l
λ
-
q
-
1
.
Substituting (33) into (28), we get
(34)
q
-
1
λ
x
l
λ
-
(
q
-
1
)
=
λ
2
x
l
-
q
x
l
⟹
λ
2
(
λ
-
(
q
-
1
)
)
x
l
-
q
(
λ
-
(
q
-
1
)
)
x
l
=
(
q
-
1
)
λ
x
l
⟹
λ
3
x
l
-
(
q
-
1
)
λ
2
x
l
-
q
λ
x
l
+
q
(
q
-
1
)
x
l
-
(
q
-
1
)
λ
x
l
=
0
⟹
λ
3
x
l
-
(
q
-
1
)
λ
2
x
l
-
(
2
q
-
1
)
λ
x
l
+
q
(
q
-
1
)
x
l
=
0
⟹
(
λ
-
q
)
(
λ
2
+
λ
-
(
q
-
1
)
)
x
l
=
0
⟹
λ
=
q
or
λ
=
-
1
±
1
-
(
-
4
(
q
-
1
)
)
2
=
-
1
±
1
+
4
(
q
-
1
)
2
.
So we have eigenvalues λ
=
q (which is the same as the degree of the vertices in the q-cliqued graph), and the conjugate eigenpairs λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2. This completes the proof of Theorem 1.This concludes the proof of the conjugate eigenpair of the adjacency matrix associated with theq-cliqued graphs, as constructed in Section 2. It is interesting to note that the conjugate eigenpair is a function of the clique number of the graph. It can also be proved that q-cliqued graphs are design graphs—see Jessop [5].In the next section, we determine the eigen-bi-balanced properties ofq-cliqued graphs associated with the conjugate eigenpair λ
=
-
1
±
1
+
4
(
q
-
1
)
/
2.


## 4. Eigen-Bi-Balanced Properties ofq-Cliqued Graphs

Now that we have determined the conjugate eigenpair for the class ofq-cliqued graphs, we can determine the eigen-bi-balanced properties, as defined in Winter and Jessop [4], for this newly defined class of graphs. We recall from Section 3 that the conjugate eigenpair is a
,
b
=
-
1
±
1
+
4
(
q
-
1
)
/
2 for all q-cliqued graphs as defined in Section 2. We will determine the eigen-bi-balanced properties of the class of q-cliqued graphs, associated with this conjugate eigenpair. We note the importance of the central vertex, which is connected to the anchor vertex of each of the q subcliques in the q-cliqued graphs. The proof of the following results can easily be verified.Theorem 2.
For the class ofq-cliqued graphs and the conjugate eigenpair a
,
b
=
-
1
±
1
+
4
(
q
-
1
)
/
2, one has the following.(1)
The class ofq-cliqued graphs is sum*
(
-
1
)
*eigenpair balanced with respect to the conjugate eigenpair a
,
b
=
-
1
±
1
+
4
(
q
-
1
)
/
2.
(2)
The class ofq-cliqued graphs is product*
1
-
q
*eigenpair balanced with respect to the conjugate eigenpair a
,
b
=
-
1
±
1
+
4
(
q
-
1
)
/
2.
(3)
The class ofq-cliqued graphs has eigen-bi-balanced ratio
(35)
r
-
1
+
1
+
4
(
q
-
1
)
2
G
K
q
*
-
1
-
1
+
4
(
q
-
1
)
2
=
1
q
-
1
,
with eigen-bi-balanced ratio asymptote(36)
r
-
1
+
1
+
4
(
q
-
1
)
2
G
K
q
*
-
1
-
1
+
4
(
q
-
1
)
2
∞
=
0
,
and density(37)
Ω
r
(
G
K
q
*
)
=
a
s
y
m
p
r
-
1
+
1
+
4
q
-
1
2
G
K
q
*
-
1
-
1
+
4
q
-
1
2
h
h
h
h
h
h
h
h
h
h
h
h
h
h
·
G
K
q
*
-
1
-
1
+
4
q
-
1
2
=
0
.
(4)
The class ofq-cliqued graphs has eigen-bi-balanced ratio area
(38)
A
r
G
K
q
*
-
1
+
1
+
4
(
q
-
1
)
/
2
,
-
1
-
1
+
4
(
q
-
1
)
/
2
=
n
-
1
(
4
n
-
1
+
4
ln
⁡
n
-
1
-
1
)
.
(5)
The class ofq-cliqued graphs has a
+
b
+
a
b
=
q with respect to the conjugate eigenpair a
,
b
=
-
1
±
1
+
4
(
q
-
1
)
/
2.Proof.
(1) The sum of the conjugate eigenpaira
,
b is
(39)
sum
-
1
+
1
+
4
(
q
-
1
)
2
,
-
1
-
1
+
4
(
q
-
1
)
2
=
-
1
+
1
+
4
(
q
-
1
)
2
+
-
1
-
1
+
4
(
q
-
1
)
2
=
-
1
.
Therefore, the class ofq-cliqued graphs is exact sum*
(
-
1
)
*eigenpair balanced. It is interesting that it is the conjugate pair of eigenvalues that satisfy the sum*
(
-
1
)
*eigenpair balanced criteria.
(2)
The product of the conjugate eigenpaira
,
b is
(40)
product
-
1
+
1
+
4
q
-
1
2
,
-
1
-
1
+
4
q
-
1
2
=
-
1
2
-
1
+
4
q
-
1
4
=
-
(
q
-
1
)
.
We have shown that the product of the conjugate eigenpair is anintegral function of q; that is, f
q
=
-
q
-
1, where q
-
1 is also the degree of the vertices in a complete graph of order q. These eigenvalues are therefore nonexact product*
1
-
q
*eigenpair balanced.
(3)
The eigen-bi-balanced ratio is(41)
r
-
1
+
1
+
4
(
q
-
1
)
2
G
K
q
*
-
1
-
1
+
4
(
q
-
1
)
2
=
-
1
-
(
q
-
1
)
=
1
(
q
-
1
)
.
Note that the eigen-bi-balanced ratio is equal to the negative of the reciprocal of the product of the conjugate pairs. The asymptote of this ratio is 0, as the value ofq increases. So
(42)
r
-
1
+
1
+
4
(
q
-
1
)
2
G
K
q
*
-
1
-
1
+
4
(
q
-
1
)
2
∞
=
0
,
Ω
r
(
G
K
q
*
)
=
asymp
r
-
1
+
1
+
4
q
-
1
2
h
h
h
h
h
h
h
h
h
h
h
h
h
h
·
G
K
q
*
-
1
-
1
+
4
(
q
-
1
)
2
=
0
.
(4)
The eigen-bi-balanced ratio area is(43)
Ar
G
K
q
*
-
1
+
1
+
4
(
q
-
1
)
/
2
,
-
1
-
1
+
4
(
q
-
1
)
/
2
=
2
m
n
∫
a
+
b
a
b
d
n
=
q
(
q
2
+
1
)
q
2
+
1
∫
-
1
-
(
q
-
1
)
d
n
=
2
q
∫
1
n
-
1
-
1
d
n
=
4
q
∫
u
d
u
u
-
1
=
4
q
∫
u
-
1
u
-
1
+
1
u
-
1
d
u
=
n
-
1
4
n
-
1
+
4
ln
⁡
n
-
1
-
1
+
c
.
Whenn
=
1 we have Ar
=
0 so that c
=
0.
So(44)
Ar
G
K
q
*
-
1
+
1
+
4
(
q
-
1
)
/
2
,
-
1
-
1
+
4
(
q
-
1
)
/
2
=
n
-
1
(
4
n
-
1
+
4
ln
⁡
n
-
1
-
1
)
.
(5)(45)
a
+
b
+
a
b
=
-
1
+
1
+
4
q
-
1
2
+
-
1
-
1
+
4
q
-
1
2
+
-
1
+
1
+
4
(
q
-
1
)
2
*
-
1
-
1
+
4
(
q
-
1
)
2
=
-
2
2
+
1
-
1
+
4
q
-
1
4
=
1
+
q
-
1
=
q
.


## 5. Design Graphs and an Entomological Experiment

The study of the interaction between insects and host-specific plants is important in biocontrol situations and is well documented—see Janz and Nylin [6]. Many such experiments use block designs (see, e.g., Coll [7]) and optimal scheduling would be advantageous when there is the occurrence of large number of treatments and blocks.


### 5.1. Design Graphs

We can associate designs with theq-cliqued graphs as follows: the vertices are the treatments and the blocks are the neighbours of each vertex (see Jessop [5]). Since we have a q-cliques graph which is a block design graph, any application of graph theory to our graphs can be applied to its associated design and in particular to experiments where block designs can be used to study the interaction of insects and plants. One of the important studies in graph theory is vertex colourings of graphs. It can be shown that a graph’s chromatic number is greater or equal to the order of its largest clique, since a complete graph on n vertices requires n colours for a proper colouring.Thus for ourq-cliqued block graphs, their chromatic number is greater than or equal to q. Jessop [5] showed that χ
(
G
K
q
*
)
=
q. We now apply a 3-colouring to the treatments of the design associated with the 3-cliqued block graph relating to an entomological experiment.


### 5.2. Experiment

We investigate the effect of 3 different species of insects on 10 different types of leaves (plants). We will have 10 cages containing the leaves and the insects, and they will be labelled as Cage 1,…, Cage 10.We have 3 sets of leaves, each containing 10 different leaves. These leaves are to be divided (arbitrarily) into 10 cages, each cage labelled Cage 1, Cage 2,…, Cage 10. Thus each type of leaf must appear 3 times in the experiment so that we need 3 sets of the 10 leaves.The effect of three species of insects (using 10 insects per species) on the leaves in each cage will be studied. The insects will be labelled. The application of the 3 different insects to the minigroups (cages) must be done in the smallest number of time sessions, such that the following conditions hold.(A1)
Each minigroup of triple leaves must be exposed to 3 different insects.
(A2)
An arbitrary minigroup of leaves will be called thecentral-trial set orcentral cage and denoted by v
1.
(A3)
There must be 3 groups of 3-cliquesP, Q, and R of cages not containing the central trial set.
(A4)
Each cage in a clique cannot receive insects at the same time.
(A5)
Exactly one member from each different clique must receive a 3-element set of insects at the same time, as well as not at the same time as the central cage receives its 3-element set of insects.
(A6)
Exactly one member of each different clique, different from the cages in (A5), must not receive a 3-element set of insects at the same time.
(A7)
The three clique groups receiving the insects must be interchangeable (permutable) so that each clique can be exposed to all 3 insects other than the control.These requirements can be depicted in a 3-cliqued graph, where its central vertex is the central-trial set. The 10 vertices (labeled 1 to 10) represent the 10 cages each containing a set of 3 leaves, the 3 leaves in each cage (vertex) having their labels from the neighbour of the vertex (this is the block of the associated design).The edges (adjacent cages) of the 3-cliqued graph represent tubes connected to the cages (vertices) with the condition that the tube cannot be open at both ends at the same time, forcing the insect into only one cage incident with the edge at a time.The 3-cliqued graph has 15 edges, each vertex incident with 3 edges so that three different insect sets of 10 insects will be used. The proper colouring of the graph will refer to the time sessions when the insects can be released subject to conditions (A1)–(A7).The chromatic number 3 refers to the condition where we require the smallest number of time sessions so that conditions (A1)–(A7) hold.The 10 blocks containing 3 different leaves from the 10 different leaves will be as follows:1:{
2,5
,
8
};
2:{
1,3
,
4
};
3:{
2,4
,
10
};
4:{
2,3
,
6
};
5:{
1,6
,
7
};
6:{
4,5
,
7
};
7:{
5,6
,
9
};
8:{
1,9
,
10
};
9:{
7,8
,
10
};
10:{
3,8
,
9
}.We colour the vertices of the graph in Figure4 as follows.Figure 4
The graph ofG
K
3
*.Put 3 colours red, green, and blue—vertex 1 coloured blue, vertices 2, 5, and 8 coloured green, vertices 4, 7, and 10 coloured blue, and vertices 3, 6, and 9 coloured red.Label the insectsi
(
1
)
,
i
(
2
)
,
…
,
i
(
30
), where i
1
+
3
k, i
2
+
3
k, and i
3
+
3
k, k
=
0,1
,
2
,
…
,
9, represent the three different species (10 each), and allocate them as follows.(1)
The trial-set is the (arbitrary) block1
=
{
2,5
,
8
}—this block contains leaves 2,5, and 8 and is coloured blue. The other blocks which are coloured blue are block 4
=
{
2,3
,
6
}; block 7
=
{
5,6
,
9
}; block 10
=
{
3,8
,
9
}. We release insects i
(
1
), i
(
2
), and i
(
3
) into cage 1, i
(
4
), i
(
5
), and i
(
6
) into cage 4, i
(
7
), i
(
8
), and i
(
9
) into cage 7, and i
(
10
), i
(
11
), and i
(
12
) into cage 10 (we only open the side incident with these vertices).
(2)
For the vertices2
=
{
1,4
,
3
}; 5
=
{
1,6
,
7
}; 8
=
{
1,9
,
10
} coloured green we release the next 9 insects (3 per vertex): i
(
13
) to i
(
21
).
(3)
For the remaining 3 vertices3
=
{
2,4
,
10
}; 6
=
{
4,5
,
7
}; 9
=
{
7,8
,
10
} coloured red, we release the remaining 9 insects (3 for each vertex): i
(
22
) to i
(
30
).With this assignment of colours inG
K
3
*, we will now show that the 7 conditions are satisfied.We have now released all the insects in the least number of time sessions of 3, each cage being exposed to 3 different insects, satisfying (A1).The central cage receives insects at a different time from a block from each clique, and these respective blocks receive insects at the same time, satisfying (A5).The 3 cliquesP, Q, and R each do not have their 3 blocks receiving insects at the same time (all blocks are adjacent in each clique) and do not contain the central cage, satisfying conditions (A3) and (A4).The edges between the cliques allow condition (A6) to be satisfied.Three 5-cycles through the central cage are each coloured with 3 colours representing the central cage not receiving insects at the same time as a cage from each block required in (A5). 2 cages from 2 separate cliques do receive insects at the same time and 2 cages from the same separate cliques do not.Once we have applied the insects with 3 different time sessions, we keep the central vertices fixed and rotate the vertices (cages) of each clique once keeping the edges (tubes) fixed releasing 27 (fresh insects other than those released into vertex 1). For example, the block represented by vertex 2 with colour green has edges (insects)i
(
13
), i
(
14
), and i
(
15
). These insects remain connected to the tubes when we rotate, but vertex 4 will replace vertex 2 or vertex 3 will replace vertex 2. This rotation allows each block of the clique to receive each of the 3 (edges of the triangle) of the clique. Keeping the edges fixed of each clique and rotating the vertices of each clique (not the colours of the vertices) and doing this for two sessions on 3-time intervals, each block of each clique will then have been exposed to the 9 insects connected to each clique.After the first two time sessions, we fix the edges (tubes) and we move the whole cliques (as vertices) around without changing the vertex colouring, so that conditions (A1), (A2) still hold, and each block other than the trial block is exposed to all 27 insects involved in the 3 cliques. Thus condition (A7) holds without violating any other condition.


## 5.1. Design Graphs

We can associate designs with theq-cliqued graphs as follows: the vertices are the treatments and the blocks are the neighbours of each vertex (see Jessop [5]). Since we have a q-cliques graph which is a block design graph, any application of graph theory to our graphs can be applied to its associated design and in particular to experiments where block designs can be used to study the interaction of insects and plants. One of the important studies in graph theory is vertex colourings of graphs. It can be shown that a graph’s chromatic number is greater or equal to the order of its largest clique, since a complete graph on n vertices requires n colours for a proper colouring.Thus for ourq-cliqued block graphs, their chromatic number is greater than or equal to q. Jessop [5] showed that χ
(
G
K
q
*
)
=
q. We now apply a 3-colouring to the treatments of the design associated with the 3-cliqued block graph relating to an entomological experiment.


## 5.2. Experiment

We investigate the effect of 3 different species of insects on 10 different types of leaves (plants). We will have 10 cages containing the leaves and the insects, and they will be labelled as Cage 1,…, Cage 10.We have 3 sets of leaves, each containing 10 different leaves. These leaves are to be divided (arbitrarily) into 10 cages, each cage labelled Cage 1, Cage 2,…, Cage 10. Thus each type of leaf must appear 3 times in the experiment so that we need 3 sets of the 10 leaves.The effect of three species of insects (using 10 insects per species) on the leaves in each cage will be studied. The insects will be labelled. The application of the 3 different insects to the minigroups (cages) must be done in the smallest number of time sessions, such that the following conditions hold.(A1)
Each minigroup of triple leaves must be exposed to 3 different insects.
(A2)
An arbitrary minigroup of leaves will be called thecentral-trial set orcentral cage and denoted by v
1.
(A3)
There must be 3 groups of 3-cliquesP, Q, and R of cages not containing the central trial set.
(A4)
Each cage in a clique cannot receive insects at the same time.
(A5)
Exactly one member from each different clique must receive a 3-element set of insects at the same time, as well as not at the same time as the central cage receives its 3-element set of insects.
(A6)
Exactly one member of each different clique, different from the cages in (A5), must not receive a 3-element set of insects at the same time.
(A7)
The three clique groups receiving the insects must be interchangeable (permutable) so that each clique can be exposed to all 3 insects other than the control.These requirements can be depicted in a 3-cliqued graph, where its central vertex is the central-trial set. The 10 vertices (labeled 1 to 10) represent the 10 cages each containing a set of 3 leaves, the 3 leaves in each cage (vertex) having their labels from the neighbour of the vertex (this is the block of the associated design).The edges (adjacent cages) of the 3-cliqued graph represent tubes connected to the cages (vertices) with the condition that the tube cannot be open at both ends at the same time, forcing the insect into only one cage incident with the edge at a time.The 3-cliqued graph has 15 edges, each vertex incident with 3 edges so that three different insect sets of 10 insects will be used. The proper colouring of the graph will refer to the time sessions when the insects can be released subject to conditions (A1)–(A7).The chromatic number 3 refers to the condition where we require the smallest number of time sessions so that conditions (A1)–(A7) hold.The 10 blocks containing 3 different leaves from the 10 different leaves will be as follows:1:{
2,5
,
8
};
2:{
1,3
,
4
};
3:{
2,4
,
10
};
4:{
2,3
,
6
};
5:{
1,6
,
7
};
6:{
4,5
,
7
};
7:{
5,6
,
9
};
8:{
1,9
,
10
};
9:{
7,8
,
10
};
10:{
3,8
,
9
}.We colour the vertices of the graph in Figure4 as follows.Figure 4
The graph ofG
K
3
*.Put 3 colours red, green, and blue—vertex 1 coloured blue, vertices 2, 5, and 8 coloured green, vertices 4, 7, and 10 coloured blue, and vertices 3, 6, and 9 coloured red.Label the insectsi
(
1
)
,
i
(
2
)
,
…
,
i
(
30
), where i
1
+
3
k, i
2
+
3
k, and i
3
+
3
k, k
=
0,1
,
2
,
…
,
9, represent the three different species (10 each), and allocate them as follows.(1)
The trial-set is the (arbitrary) block1
=
{
2,5
,
8
}—this block contains leaves 2,5, and 8 and is coloured blue. The other blocks which are coloured blue are block 4
=
{
2,3
,
6
}; block 7
=
{
5,6
,
9
}; block 10
=
{
3,8
,
9
}. We release insects i
(
1
), i
(
2
), and i
(
3
) into cage 1, i
(
4
), i
(
5
), and i
(
6
) into cage 4, i
(
7
), i
(
8
), and i
(
9
) into cage 7, and i
(
10
), i
(
11
), and i
(
12
) into cage 10 (we only open the side incident with these vertices).
(2)
For the vertices2
=
{
1,4
,
3
}; 5
=
{
1,6
,
7
}; 8
=
{
1,9
,
10
} coloured green we release the next 9 insects (3 per vertex): i
(
13
) to i
(
21
).
(3)
For the remaining 3 vertices3
=
{
2,4
,
10
}; 6
=
{
4,5
,
7
}; 9
=
{
7,8
,
10
} coloured red, we release the remaining 9 insects (3 for each vertex): i
(
22
) to i
(
30
).With this assignment of colours inG
K
3
*, we will now show that the 7 conditions are satisfied.We have now released all the insects in the least number of time sessions of 3, each cage being exposed to 3 different insects, satisfying (A1).The central cage receives insects at a different time from a block from each clique, and these respective blocks receive insects at the same time, satisfying (A5).The 3 cliquesP, Q, and R each do not have their 3 blocks receiving insects at the same time (all blocks are adjacent in each clique) and do not contain the central cage, satisfying conditions (A3) and (A4).The edges between the cliques allow condition (A6) to be satisfied.Three 5-cycles through the central cage are each coloured with 3 colours representing the central cage not receiving insects at the same time as a cage from each block required in (A5). 2 cages from 2 separate cliques do receive insects at the same time and 2 cages from the same separate cliques do not.Once we have applied the insects with 3 different time sessions, we keep the central vertices fixed and rotate the vertices (cages) of each clique once keeping the edges (tubes) fixed releasing 27 (fresh insects other than those released into vertex 1). For example, the block represented by vertex 2 with colour green has edges (insects)i
(
13
), i
(
14
), and i
(
15
). These insects remain connected to the tubes when we rotate, but vertex 4 will replace vertex 2 or vertex 3 will replace vertex 2. This rotation allows each block of the clique to receive each of the 3 (edges of the triangle) of the clique. Keeping the edges fixed of each clique and rotating the vertices of each clique (not the colours of the vertices) and doing this for two sessions on 3-time intervals, each block of each clique will then have been exposed to the 9 insects connected to each clique.After the first two time sessions, we fix the edges (tubes) and we move the whole cliques (as vertices) around without changing the vertex colouring, so that conditions (A1), (A2) still hold, and each block other than the trial block is exposed to all 27 insects involved in the 3 cliques. Thus condition (A7) holds without violating any other condition.



---

*Source: 152918-2015-03-02.xml*