SPECTRAL GRAPH THEORY

Dissertation submitted in the partial fulfillment of the requirement for the the

MASTER’S DEGREE IN MATHEMATICS

By

FATHIMA A S
Reg No:210011014841

Under the guidence of

Toby B Antony

Department of Mathematics

BHARATA MATA COLLEGE,THRIKKAKARA

(Affiliated to Mahathma Gandhi University,Kottayam)

2021-2023

1
 DECLARATION

I Fathima A.S hereby declare that this project entitled ’SPECTRAL

GRAPH THEORY’is a bonafide record of work done by me under the
guidence of Toby B Antony ,asociate proffesor on contract Department
of Mathematics, Bharata Mata College, Thrikkakara and this work has
not previously formed by the basis for the award of any academic quali-
fication, fellowship or other similar title of any other University or Board

Fathima A.S
Msc Mathematics
Bharata Mata college,Thrikkakara

Place:Thrikkakara
Date:

2
 CERTIFICATE

This is to certify that the project entitled SPECTRAL GRAPH THE-

ORY submitted for the partial fulfillment requirement of Degree in
Mathematics is the original work done by Fathima A.,S during the pe-
riod of the study in the Department of Mathematics, Bharata Mata
College, Thrikkakara under my guidance and has not been included in
any other project submitted previously for the award of any degree.

Toby B Antony
supervisor
Place:Thrikkakara
Date:

3
 ACKNOWLEDGEMENT

First and foremost I express my sincere gratitude towards the abiding

presence and grace of God Almighty.

I sincerely express my gratitude to Toby Antony sir, Associate Profes-

sor, Department of Mathematics, Bharata Mata College, Thrikkakara
for guiding and helping me to complete this work.

I also express my profound gratitude to Dr. Lakshmi.C , Head of the

Department of Mathematics, Bharata Mata College, Thrikkakara for
her wholehearted cooperation and valuable advices.

Finally, I am much obliged to all our teachers of the Mathematics De-

partment, Bharata Mata College for the encouragement for completing
this work.

FATHIMA A S

4
 INTRODUCTION

Spectral graph theory is the branch of mathematics that studies the

properties of a graph in relationship to the characteristic polynomial,eigen
values,and eigen vector of matrices associated with graph and spectrum
of its adjacency matrix or Laplacian matrix.Initially, spectral graph the-
ory examined a graph’s adjacency matrix, particularly its eigenvalues.
Many advancements over the past 25 years have tended to be more ge-
ometric in nature, such as random walks and quickly shifting Markov
chains.

Deducing the fundamental characteristic and structure of a graph from

its invariants is a key objective of a graph theory. Nearly all important
network invariants have strong ties to the eigen values. They include a
plethora of graph related knowledge. This is the focus of spectral theory.

There is a lengthy history of spectral graph theory. The 1950s and 1960s
saw its emergence. The relationship between graph theoretical study and
research in quantum chemistry,which wasn’t found until much later,was
another important source. Additionally,graph spectra naturally appear
in a veriety of theoretical physics topics. Eigen value application can be
found in many context and under several names. However it is possible
to think of the underlying mathematics of spectral graph theory as a
5
single,cohesive item.

We aim to investigate the core of graph theory in this project. We start

out by defining some fundamental graph theory terms. The spectra of
a few fundamental graphs are then determined when we introduce the
adjacency and Laplacian matrices. We also examine several spectral
characteristic and related theorems. The paper ends with a few intrigu-
ing spectral graph theory applications.

6
Chapter 1

PRELIMINARIES

1.1 GRAPH

Definition 1.1 A graph G is a pair (V,E) where V is a non- empty set

whose elements are called the vertices of G and E is a sub set of V whose
elements are the edges of G and a set of edges,E,where each edge is an
unordered pair of vertices.

Graphs can be represented pictorially as a set of nodes and a set of lines

between nodes that represent edges. We say that a pair of vertices,Vi
and Vj are adjacent if Vi, Vj ∈ E where Vi, VJ represents the edge be-
tween them. Any two adjacent vertices are neighbours and the set of
all neighbours of a vertex v in G is denoted by NG(V). This graph is an
undirected graph. A directed graph is similar to undirected graph except
that each edge is assigned an orientation and so we have E ⊂ V × V.

Definition 1.2 Cardinality of the vertex set is called order of G and the
7
cardinality of the edge set is called the size of G. A graph is finite if both
its vertex set and edge is finite.[3]

Definition 1.3 A loop is an edge that is incident with the same vertex
twice. Parallel edges occur when there are two or more distinct edges
between the same two vertices. A graph is said to be simple if it has no
loop or parallel edges.

Definition 1.4 A complete graph, often known as a clique, is a simple

graph with any two vertices adjacent. It is denoted by Kn.

Definition 1.5 If a graph’s vertex set can be divided into two subgroups,
X and Y , with each edge having one end in each subset, that graph is
said to be bipartite. A bipartition of the graph and X and Y is what is
referred to as such a partition (X,Y).G is referred to as complete bipar-
tite if it is a simple bipartite graph with the bipartition (X,Y) such that
every vertex in X is connected to every vertex in Y . It is denoted by
Kn,n[3]

8
Definition 1.6 A Star is a complete graph with|X| is one or|Y| is one.Given
below is an example of complete graph,a complete bipartite graph,and
star.

Definition 1.7 The number of edges in a graph G that are incident with
a vertex, denoted as de(v), represents the degree of that vertex. Each loop
in the graph is counted twice.
especially if G is a straightforward graph. The number of neighbors is
de(v) in G of v.

9
 A graph G is k regular if d(v) = k; ∀ v ∈G . A regular graph is the
one that isk regular for some k. For example, the complete graph on n
vertices is (n-1) regular.

Definition 1.8 An alternately placed series of edges and vertices that

starts and ends with a vertex is referred to as a walk, n edges make up
a walk of length n. A walk is referred to as a trail if all of its edges are
distinct. a path is referred to as having all of its vertices being distinct.

And so a path is a simple graph whose vertices can be arranged in a

linear sequence in such a way that two vertices are adjacent if they are
consecutive in the sequence and are non adjacent otherwise. Likewise, a
cycle on three or more vertices is a simple graph whose vertices can be
arranged in a cyclic sequence such that two vertices are adjacent if they
are consecutive in the sequence and are non adjacent otherwise.[1]

The length of a path or a cycle is determined by the number of its

edges. We denote by P , the path on n vertices and by C , the cycle on
n edges.

Definition 1.9 Every pair of vertices in graph G is referred to as being

connected if a path connects them. The term "connected component" or
"component of G" refers to a maximally connected subgraph of G. Thus
10
a disconnected graph has atleast two components.

The distance between two vertices u and v of G is defined as the length

of the shortest path from u to v.

The eccentricity of a vertex is given by e(v)=max{d(u,v):u∈ V,u̸ =

v} and diameter of a graph G is the maximum of the eccentricities of
the vertices in G.

Definition 1.10 Empty graph: An empty graph on n vertices con-

sists of n isolated vertices with no edges. The empty graph on n vertices
is the graph complement of the graph Kn

Line graph: Let G be a loopless graph. Its line graph, L(G) is aa graph
whose vertex set is in 1-1 correspondence with the edge set of G and two
vertices of L(G), and 2 vertices of L(G) are adjacent iff the correspond-
ing edges in G are adjacent.

A graph is completely defined by either their adjacencies or its in-

cidence, this information can be conveniently stated in matrix form.
Indeed, with a given graph,adequately labled,there are associated sev-
eral matrices.
We shall now define the adjacency matrix and the incidence matrix of a
11
graph. Without loss of generality assume that G is a graph with vertex
set V= {1,2,...,n}

1.2 Adjacency Matrix

Definition 1.11 The adjacency matrix of a graph G is an n x n matrix

AG =(aij ) where.for i,j ∈1,2,..n

(
1, i, j∈ E
aij =
0, otherwise.

The i,j th entry of the matrix denotes the number of edges joining the
vertices i and j. Also,we count each loop twice.

For example consider the graph G:

12
The adjacency matrix is given by AG =
 
0 1 1 0
 
1 0 1 0
 
 
1 1 0 1
 
0 0 1 0

Clearly, for any graph we may write the adjacency matrix in different
ways, by changing the ordering of vertices. We observe that ai,j =aj,i ∀
i,j in the adjacency matrix. Thus, the adjacency matrix of any graph is
symmetric. In addition if G is simple, then every entry in AG will be
either 0 or 1 with 0s on the diagonal.

1.3 Incidence Matrix

Definition 1.12 Let G be a graph with vertex set V = {1,2,...,n} con-

sisting of m edges.The incidence matrix of G is an n×m matrix IG =(bve)
where bve denotes the number of times the vertex v is incident with edge e.

Consider the graph:

13
The incidence matrix is given by
 
1 1 0 0
 
1 0 1 0
 
0 1 1 2

Theorem 1.1 In a graph G with vertex set V ={1,2,...,n} A be its

adjacency matrix. The entry Ani,j of the matrix A equals the number of
i-j walks oflength n.

Proof: The proof follows by induction, When n=1, the entry ai,j of A is
the number of edges between i and j which is nothing but the number
of walks in G of length 1.
Now assume that the result(holds for n-1. We have,An = An−1A So,
1, (i, j)∈ E
ani.j = nk=1 an−1
P
i,j ai,j ai,j =
0, otherwise.

it follows that aik aj represents the number of those i-j walks that
are formed by joining the edge (k.j) to the i-k walks of length n-1 in G.
therefore An−iA is summation of all walks of length n-1 from vertex I to
any other vertex that is adjacent to j. this is equivalent to the number
14
of n walks from i to j. Thus the theorem holds by induction.

Theorem 1.2 Trace of A2 is twice the number of edges in the graph.

Proof: Let G be a graph with order n and size m. Let A be the adjacency
matrix and let vi be an arbitrary vertex of G. For every edge vivj of G,
by theorem 1 we get a count 1 towards the (i,i) th position of A2. That
is, the (i,i) th position of A2is equal to the degree of vi since every vivj
walk of length 2 will be a single edge vivj of G. Hence,
2
P
Tr(A )= v∈v(G)d(vi) = 2m.

Theorem 1.3 Trace of A3 is six times the number of triangles in the

graph.

Proof: Let G be a graph with order n and size m, A be the adjacency

matrix of G and let vi be an arbitrary vertex. For every 3 cycle vivj vk vi
of G, by theorem 1. we get a count of I towards the (i,i) th position
of A3. That is, the (i, i)th position of A3 which denotes the number of
walks of length 3 starting and ending at vi is equal to the number of 3
cycles that start and end at vi. Since the vertices of the 3 cycle vivj vk vi
can be ordered in six ways, we can conclude that trA3 is six times the
number of triangles in G.

15
1.4 Characteristic Polynomial and Eigenvalues

The characteristic polynomial,Γ of a graph of order n is the polynomial

Det (λI-A) where I is the nidentity matrix and A is the adjacency matrix
of the graph.
consider the graph,

we have the adjacency matrix as

 
0 1 1
 
1 0 1
 
1 1 0

the characteristic polynomial is Γ = det(λI-A) =

λ −1 −1
−1 λ −1
−1 −1 λ

= λ3-3λ-2

16
 The characteristic polynomial has the general form λn+c1λn−1+...+cn.This
polynomial enormously important to spectral grapy theory since it is an
algebraic construction that contains graphical informations.The roots of
the characteristic polynomial are calledEigen values. The Eigen value
or characteristic value of matrix A is a scalar λ such that there is a non
zero vector x satisfying Ax=λx.

Any non zero vector x satisfying Ax = λ x is called an Eigen vector

or characteristic vector of A associated with the characteristic value λ.
In the above example if we equate the characteristic polynomial to
zero ie.λ3-3λ-2,and solve we will get the eigen values as {1,-1,2}.

17
Chapter 2

THE SPECTRUM OF GRAPHS

Definition 2.1 The set of a matrix’s eigenvalues and their multiplicities

is known as the spectrum of the matrix. The spectrum of an adjacency
matrix equals the spectrum of the graph. The adjacency matrix’s eigen-
values and eigenvectors are therefore regarded as the graph’s eigenvalues
and eigenvectors.

Suppose G is a graph.Let {λ1,λ2,...,λt} be the eigenvalues of its adja-

cency matrix with multiplicities m1,m2,...,mt respectively
Then we write
(m1 ) (m2 ) (mt )
Spec(G)= { λ1 ,λ2 ,...,λt } or

Spec(G)= !
λ1 λ2 ...,λt
m1 m2 ...mt
18
2.0.1 Result

A graph with n vertices have n eigen values.

Proof: This is a direct consequence of the algebraic fundamental the-

orem. The characteristic polynomial of a graph with n vertices is a
polynomial of degree n, and according to a fundamental algebraic the-
orem, any polynomial of degree n in the area of complex numbers has
n roots, counting multiplicity. The graph consequently has n eigenvalues.

For example,consider the graph

Here , A=  
0 1 1 0
 
1 0 0 1
 
 
1 0 0 1
 
0 1 1 0
The characteristic polynomial of the adjacency matrix is λ4-4λ2 and the
eigen values are {0,0,2,-2}. The graph has three distinct eigen values,-
2,2,0.
Spec(G)= {-2,0(2), 2}.
19
2.1 Spectrum Of Some Fundamental Graphs

In this section we determine the spectra of some fundamental graphs.All

the graph considered are find,undirected and simple.

2.1.1 The Graph(Kn)

It denotes the empty graph on n vertices.

Since the graph has no edges,adjacency matrix is,

A=  
0 ... 0
 
 ... ... ... 
 
0 ... 0
In this case if we consider any non zero vector X in Rn,the equation
Ax= λx will imply that λ=0.Thus λ=0 is the only possible eigen value
of A.Since the graph has n vertices it must have n eigen values.Hence we
can conclude that zero is the only eigen value of (Kn) with multiplicity
n.
Sp(Kn) = {0n}

20
2.1.2 The Complete Graph (Kn)

In a complete graph,each vertex is joined to every other vertex by an

edge.So the adjacency matrix will have diagonal entries 0 and all other
entries will be 1.
A=  
0 1 1 ... 1
 
 1 0 1 ... 1 
 
 ... ... ... ... ... 
 
 
 ... ... ... ... ... 
 
1 1 1 ... 0
A is a circulant matrix of order n.
Lemma 2.1 Let A a circulant matrix of order n with first raw (a1,a2,..,an)
then Sp(A)={ a1+a2ω 2+...+anω n−1,ω= an nth root of unity.}

proof: The characteristic poynomial of A is determinant D=det(xI-

A).Hence,
D=  
x−a1 −a2 ... −an
 
 −an x−a1 ... −an−1 
 
 ... ... ... ...  Let
 
 
 ... ... ... ... 
 
−a2 −a3 ... x−a1
ci denote the ith column of D,1≤i≤n and ω,an nth root of unity.Replace
Ci by C1+C2ω+...+Cnω n−1.This does not change D.
21
Let λω = a1+a2ω+...+anω n−1.Then the first new column of D is
(x-λω ,ω(x-λω ),...,ω n−1(x−λω ))T , and hence x-λω isa factor of D.This
gives D= ω (x-λω ) and Sp(A) ={λω :ω n=1}.
Q

Applying this lemma we get,here (a1,a2,...,an)=(0,1,1,...,1).

(
n − 1, if, ω = 1
λω =
−1, if, ω ̸= 1
hence, Spec(Kn)={(-1)n−1, (n − 1)}

2.1.3 Cycle (Cn )

Consider Cn.The adjacency matrix is given by,

A=  
0 1 0 ... ... ... 0 1
 
 1 0 1 ... ... ... 0 0 
 
 
 ... ... ... ... ... ... ... ... 
 
 ... ... ... ... ... ... ... ... 
 
 
 0 0 0 ... ... ... 0 1 
 
1 0 0 ... ... .... 1 0
Clearly A is circulant with first row (010...01). So by lemma 2.2.3, the
eigenvalues of A are of the form a0=a1ω+a2ω 2+....+anω n−1 = ω+ω n−1.
2πik
The nth root of unity has the form,ω= e n ,k=0,1,...,n-1
2πik 2πik
ω+ω n−1 = e n +((e n )n−1) = 2cos 2πk
n ,k= 0,1,...,n
hence,
22
Spec(Cn) = {2cos 2πk
n ; k=0, 1, ..., n}

2.1.4 Complete Bipartite Graph

Lemma 2.2 Let G be a graph of order n and size m, and let Γ(G, x)
=xn+a1xn−1+...+an be the characteristic polynomial of G.then,

(1)a1 = 0
(2)a2 = -m
(3)a3 = -(twice the number of triangles in G)

Proof: A be the adjacency matrix of G. From direct verification we

have(−1)r = sum of the principal minors of A of order r.
(1) Also we know the principal diagonal entries of A are all 0. Hence
result follows directly.
(2) A non vanishing principal minor of order 2 of A is of the form

0 1
1 0

and its value is -1. Also this actually corresponds to an edge of G.

hencea2 =-1×(number of principal minors of the above form) = -m.
(3) A non trivial principal minor of order 3 of A can be one out of the
23
following three types.
0 1 0
1 0 0
0 0 0

0 1 1
1 0 0
1 0 0

and
0 1 1
1 0 1
1 1 0

0ut of these only last determinant is non vanishing.Its value is 2 and it

corresponds to a triangle in G.This proves (3). Now consider a complete
bipartite graph Km,n let V have the partition (X,Y) with |X|=m and
|Y | = n. then the adjacency matrix of the for
A= " #
0 Jm,n
Jm,n 0

Where Jr,s stands for all 1-matrix of size r by s. clearly, rank(A)=2, as

the maximum number of independent rows of A is 2. We know,
dim(A)= m+ n = rank(A) + nullity(A).

Hence nullity(A) = multiplicity of eigen value λ=0=m+n-2 i.e. 0 is

24
an eigen value of A repeated m+n-2 times.

Now we can say that the characteristic polynomial of km,n will be,
Γ = λm=n−2(λ2 + Q). To find Q we use lemma 2.2.6 and obtain Q =
coefficient of λm=n−2=-(number of edges) = -mn. λm+n−2(λ−2-mn)=0 is
the characteristic polynomial. λ−2-mn= 0.
√
λ = mn
Hence
√ √
SpecKm,n = {0m+n−2 mn,- mn}

2.1.5 Path(Pn)

We will find a recurrence relationship for the characteristic polynomial

of a path graph. Recall that the adjacency  matrix of a path graph P. is
0 1 0 0 ... ... ... 0 0
 
 1 0 1 0 ... ... ... 0 0 
 
 
 ... ... ... ... ... ... ... ... ... 
A(Pn)= W hereai,j = 1 if |i−j| = 1,and
 ... ... ... ... ... ... ... ... ... 
 
 
 0 0 0 0 ... ... ... 0 1 
 
0 0 0 0 ... ... ... 1 0
ai,j = 0 otherwise.
To find the eigenvalues of the adjacency matrix we need to find charac-
teristic equation of the matrix A(Pn)
25
  
λ −1 0 0 ... 0 0
 
 −1 λ −1 0 ... 0 0 
 
 0 −1 λ −1 ... 0 0
 

 
 ... ... ... ... ... ... ... 
(λI-A(Pn))=
 

 
 
 ... ... ... ... ... ... ...
 

 
 
 
0 0 0 0 ... −1 λ

Thus det(λI-A)= λdet(λI-A(Pn−1)) − det(λI-A(PN-2))

Let fk be the characteristic polynomial of A(pk ) so that we get the re-
currence relation
fk = λfk−1-fk−2.
For P1,f1=λ and adjacency spectrum is {0}
For P2,f2 = λ2-1 and spectrum is { 1,-1} For p3 ,f3 = λ3-2λ and the
√ √
spectrum is {0, 2,- 2 }
We do not show how to obtain spectrum of path from this equation and
instead give result from Godson and Royle.[2]
πk
spec(pn) = 2cos n+1 ,where k=1,2,...,n

2.2 Cospectral Graphs

A question that arises is that can we say that two graphs are isomorphic
by simply inspecting their spectra.The answer is no,because there do
26
exist pairs of non isomorphic graphs with the same spectrum.

Definition 2.2 Graphs with same adjacency spectrum is called cospecral

or isospectral graphs.

Example is given below;

Spec(G1) = !
−2 0 2
1 3 1

Spec(G2) = !
−2 0 2
1 3 1

Thus G1 and G2 have same spectrum. But they are not isomorphic.

2.3 SPECTRAL PROPERTIES

The computation of the spectrum was our main focus in the preceding
part. We’ll now examine how a graph’s attributes and spectrum relate
27
to one another. Since the spectrum of a disconnected graph is the union
of the spectra of its components, we immediately note that we only need
to consider connected graphs.

Definition 2.3 If the spectrum of a graph G is { λm1 m2 mk

1 ,λ2 ,...,λk } its
minimal polynomial is m(G:λ) = ki−1 (λ-λi) and m(G:A) = 0.And the
Q

degree of minimal polynomial is the number of distinct eigen values oh

G.

Lemma 2.3 A graph G has 1 distinct eigen value if and only if G has
no edges.

Proof: Assume G only has one unique eigenvalue. The adjacency matrix
will be a scalar multiple of the identity matrix since the characteristic
polynomial of G has degree I in that case. G will therefore be edgeless.
In contrast, G will only have one eigenvalue if it lacks any edges.

Lemma 2.4 The complete graph G is determined by its spectrum.

Proof: According to our knowledge, a graph with n vertices has n eigen-

values, and the complete graph is the only connected graph with pre-
cisely two different eigenvalues. Therefore, if a graph’s spectrum con-
tains precisely two different eigenvalues, we can say that the graph is
28
complete. The number of graph vertices is determined by the eigenvalue
multiplicities

29
Chapter 3

THE LAPLACIAN MATRIX OF A

GRAPH

Another significant matrix connected to a graph is the Laplacian, and

the Laplacian spectrum is the spectrum of this matrix. The Kirchhoff
matrix and the information matrix are two more names for the Lapla-
cian matrix. In a manner similar to the spectral graph theory explored
in the preceding parts, we will look at the relationship between a graph’s
structural characteristics and the Laplacian spectrum in this section.

3.1 Definition

The Laplacin matrix L(G)=(Li,j ) of a graph G on n vertices is an n×n

matrix whose entries are given by,

30
 
 d(i) if i=j


Li,j = −1 if i̸=j


0 otherwise

For example consider G

The Laplacian matrix of G is

 
2 −1 −1 0
 
 −1 2 −1 0 
 
 
 −1 −1 3 −1 
 
0 0 −1 1

We can define the degree matrix of G as n×n diagonal matrix. D=

(mi,j ),where,

(
d(i) if i=j
mi,j =
0 otherwise

then we can define laplacian matrix L as L=D-A.

31
3.2 Properties Of the Laplacian matrix

1.A graph’s Laplacian matrix is symmetric and has real entries. L=L∗,
and it is hence self adjoint. Furthermore, we are aware that a self adjoint
matrix’s eigenvalues are actual. Therefore, all of the Laplacian matrix’s
eigenvalues are real.
2.The row sums as well as the column sums of the Laplacian matrix are
0. This is because when we consider any row or column the diagonal
entries of the matrix are degrees of the vertices and every incident edge
contributes -1.
3.0 is always an eigenvalue. This follows from the fact that all the row
sums are 0 and all the 1s vector is eigen vector for the eigen value 0.
4.The laplacian matrix is positive semidefinite.
A matrix M of order n×n is said to be positive semi definite if ,
X T X ≥ 0.∀x ∈ Rn.
Here we have X T X = i,j Xi li,j Xj = i,j li,j Xi Xj
P P

= i d(i)li,j Xi2+2 (i,j)∈E łi,j Xi Xj + i,j ∈/ E li,j Xi Xj

P P P

= i d(i)X 2+2 i,j ∈E (−1)XiXj + i,j E 0Xi,Xj

P P P

= i,j ∈E (Xi-Xj )2≥0,∀x ∈Rn

P

Every eigenvalue of a graph G’s Laplacian matrix is positive. Suppose

L has an eigenvalue of λ, and the related eigenvector x ∈ R is non zero,
L x =λ x.
Afterward, xT Lx=xT λx = λ ||x||2 We need to have λ ≥ 0 sincexT Lx≥
0 and ||x||2>0Every eigenvalue of a graph G’s Laplacian matrix is pos-
32
itive.
P n
i =1 λi =trace(LG )= sum of degrees of vertices in G.=2m,where m is
the number of edges of graph G .

Pn 2
Pn Pn
i=1 λi = trace(L2G)= i=1 [d(i)
2
+ d(i)]=2m+ i=1 d(i)
2

We can also define Laplacian as follows,

Assume that the graph G (V,E) has an edge set E={e1, e2,..., em| and
a vertex set V={V1, V2,..., Va}. Select one of the vertices v, or v, as
the positive "end" of e and the other as the negative "end" for each edge
ej= (V, Vk). So, each edge in G now has an orientation. The outcome
is unaffected by the orientation that is randomly assigned to each edge
of G in this case.

The incident matrix ,afforded by the orientation is called the signed

incident matrix of G.And it is defined as,


1 if v1 is the positive end of e1


qi,j = −1 if v1 is the negative end of e1


0 otherwise

Then the laplacian matrix is given by L=QQT .Consider the folloing

graph,

33
 We have assigned an orientation to each edge of graph as shown in
the figure,the tail of each arrow is chosen as the negative end and head
as the positive end.
Q=  
−1 0 −1 0
 
 1
 −1 0 0 

 
 0
 1 1 −1 

0 0 0 1

QT =  
−1 1 0 0
 
 0
 −1 1 0 

 
 −1 0 1 0
 
0 0 −1 1

34
 QQT =  
2 −1 −1 0
 
 −1 2 −1 0 
 
 
 −1 −1 3 −1 
 
0 0 −1 1

QQT = L

3.3 Laplacian spectrum of some graphs

Consider the graph,

G is 2 regular and,
A=  
0 1 1
 
1 0 1
 
1 1 0
35
 Its eigen vsalues are λ1 = -1,λ2 = -1,λ3 = 2.
the laplacian matrix is L = 2I-A =
 
2 −1 −1
 
 −1 2 −1 
 
−1 −1 2

det(L-λ̃I) = 0
λ̃3-6λ̃2+9λ̃ = 0
λ̃1 = 1,λ̃2 = 3,λ˜3 = 0.

Hence we have the result,If G is a k regular graph with adjacency

matrix A and laplacian matrix ,then L=D-A =KI-A . Let λ1,λ2,...,λn be
the eigen values os A.Then the eigen values of L will be k-λ1,k-λ2,...,k-λn.

3.3.1 The complete graph

The complete graph is (n-1) regular.We had seen that ,

Spec(Kn)={(-1)(n − 1), (n − 1)}
SpecL(Kn)={0,(n)(n−1) }
We see that for the complete graphs, all non zero eigen values coin-
cide.The greatest is n which is also the graph order.

36
3.3.2 The cycle (Cn )

Cn is a 2 regular graph.We have, Spec(Cn) = {2cos 2πk

n ;k=0,1,...,n}
SpecLCn = { 2-2cos 2πk
n ;k=1,2,...,n}

Theorem 3.1 Let G be a graph with V (G)={ 1,2,...,n}. Let W be a

nonempty proper subset of V (G). Then the determinant of L(W|W)
equals the number of spanning forests of G with W components in which
each component contains one vertex of W.[4]

Proof. Assign an orientation to each edge of G and let Q be the incidence

matrix. We assume, without loss of generality, that W = {1,2,...,k}. By
the Cauchy-Binet formula,
det L(W|W)= (detQ[Wc, Z])2
P

where the summation is over all Z⊂E(G) with |Z|=n-k.

Since by Lemma Q is totally unimodular, then (detQ[Wc,Z])2 equals
0 or 1.
Thus, det L(W|W) equals the number of nonsingular submatrices of
Q with row setW c
In view of the discussion in Section Q[W c, Z] is nonsingular if and
only if each component of the corresponding substructure is a rootless
tree. Hence, there is a one-to-one correspondence between nonsingular
submatrices of Q with row set We and spanning forests of G with |W|
components in which each component contains one vertex of W.[4]
37
Theorem 3.2 Let G be a graph with V (G)= {1,2,...,n}. Then the co-
factor of any element of L(G)equalsthenumberof spanningtreesof G.[4]

Proof. Setting W={1} in the above theorem it follows that det L(1|1)
equals the number of spanning forests of G with one component, which
is the same as the number of spanning trees of G. By Lemma all the
cofactors of L(G) are equal and the result is proved.[4]

3.4 ENERGY OF GRAPHS

Definition 3.1 Energy of graph is defined as the sum of absolute values

of the adjacency matrix of the graph.

38
Chapter 4

APPLICATIONS

4.1 Epidemic Spread In Networks

Graphs can be used to explore the issue of virus spread and are frequently
utilised as abstract representations of various networks. According to the
susceptible. invective-susceptible (SIS) model, each node of a network
(vertex of a graph) may be in one of two states: healthy yet susceptible
to infection (S) or infected (I), with the latter having the potential to
propagate illness to susceptible nodes in the network. A person who is
sick can also be treated locally, making them susceptible once more. A
rate of infection is connected with each edge, and a virus curing rate of
six is associated with each infected node. A directed edge from node i
to node j indicates that i can infect.The epidemic threshold of a graph
G i the value τ such that if βδ <τ then the viral outbreaks dies out over
time and if not the infection survives.let G be a graph representing this
network.During each time interval , an infected node I tries to infect its
neighbour’s with probability β . At the same time node I can be cured
with a probability δ.
39
 1
Then, the epidemic threshold of G equals λ1 (G) . where λ1(G) denotes
the largest eigen value of the adjaceny matrix of G. An infected node I
attempts to infect its neighbours with probability at each time period.
Additionally, there is a chance of curing node I.

4.2 Graph Coloring

Vertex-coloring, or the process of giving different colours to a graph’s

vertices so that no two adjacent vertices have the same colour, is one of
the fundamental issues in graph theory. The goal is to utilise the fewest
colours feasible. The fewest colours required for such a split is known as
the correct chromatic number of a graph G.χ(G) is the least number of
colours required for such a partition. The graph’s spectrum provides us
with information on the chromatic number, which is at the core of graph
colouring. The boundaries of G’s chromatic number are determined by
if G has n vertices. ,
λ1
1+ −λ n
≤ χ(G) ≤ 1+λ1

4.3 Spectral clustering

An essential part of the study of electrical network connections is clus-

ter identification. This is where the graph spectral approach comes in
very handy because it allows us to quickly compute the results we re-
quire. Edge weights serve as entries in an adjacency matrix. The weights
40
are d1i,j di,j represented by is the distance between vertices i and j.
The objective is to locate the vertices so that the weighted sum of the
squared distances between them is as small as possible. The entire pro-
cedure won’t be covered here, but the main point of importance is that
the clustering sites in the graph are determined by the vector compo-
nent of the Laplacian matrix’s second-smallest eigenvalue. The second
smallest eigen value for the clustered vertices is the same. Also, only
one of the clusters is represented by the biggest eigen value.

4.4 Information Technology

About 10 years ago, it became apparent that graph spectra have numer-
ous significant applications in computer science. Internet technologies,
pattern recognition, computer vision, data mining, multiprocessor sys-
tems, statistical databases, and many other fields all make use of graph
spectra.
The eigenvectors of the adjacency and several related graph matrices
provide the foundation of web search engines. Web sites serve as the
vertices of a digraph G that depicts the structure of the Internet, while
hypertext links between pages serve as its arcs. The Hyperlinked In-
duced Topics Search (HITS) algorithm takes advantage of the eigenvec-
tors that correspond to the greatest eigenvalues of the matrices AAT and
AAT , where A is the adjacency matrix of a subgraph of G induced by
the collection of websites that certain heuristics have identified from the
41
set of search-keyword-derived webpages. A particular ordering of the
chosen webpages is determined by the obtained eigenvectors. In mod-
elling viral spread in computer networks, the adjacency matrix’s biggest
eigenvalue λ1 of A is crucial. The resilience increases with decreasing
greatest eigenvalue

42
 CONCLUSION

The primary purpose of spectral graph theory is to connect essential

structural aspects of a graph to their eigenvalues. It is a developing
branch of mathematics having several applications in various fields of
study. The major goal of this study was to teach some of the funda-
mental concepts of spectral graph theory, with a particular emphasis on
how to discover the spectra of various types of graphs. We also talked
about the Laplacian matrix that is connected with a graph. There is a
lot more to say about Laplacian spectrum.
In fact, it is outside the oversight of this work to conduct a "complete"
survey of all the literature on the Laplacian spectrum. We also showed
how the biological, and computer sciences can benefit greatly from the
spectrum of graphs. Spectral graph theory can be used to model a va-
riety of real-world issues. There are numerous sciences and other fields
where linear algebra, graph theory, and the spectrum of an are used.

43
Bibliography

[1] @bookbrouwer2011spectra, title=Spectra of graphs, au-

thor=Brouwer, Andries E and Haemers, Willem H, year=2011,
publisher=Springer Science & Business Media

[2] @bookgodsil2001algebraic, title=Algebraic graph theory, au-

thor=Godsil, Chris and Royle, Gordon F, volume=207, year=2001,
publisher=Springer Science & Business Media

[3] @bookbalakrishnan2012textbook, title=A textbook of graph the-

ory, author=Balakrishnan, Rangaswami and Ranganathan, Kanna,
year=2012, publisher=Springer Science & Business Media

[4] @bookbapat2010graphs, title=Graphs and matrices, author=Bapat,

Ravindra B, volume=27, year=2010, publisher=Springer

44