SPECTRUM OF GRAPH

A project report submitted to Christ College (Autonomous) in partial fulfillment of

requirement for the award of the B.Sc. Degree Programme in Mathematics(Self)

By
Shahma Salim-CCATSMT060

DEPARTMENT OF MATHEMATICS(SELF)

CHRIST COLLEGE (AUTONOMOUS)

Irinjalakuda

2022

1
 CERTIFICATE

This is to certify that the project entitled “Spectrum of Graph” submitted to the Department
of Mathematics in partial fulfillment of the requirement for the award of the B.Sc. Degree
programme in Mathematics, is a bonafide record of original research work done by Shahma
Salim(CCATSMT060), during the period of the her study in the Department of Mathematics,
Christ College (Autonomous), Irinjalakuda under my supervision and guidance during the year
2021-2022.

Mrs. Akshara.R Dr. Joju. K.T

Adhoc Lecturer
Department of Mathematics HOD
Christ College (Autonomous) Department of Mathematics (Self)
Christ College (Autonomous)
Irinjalakuda
Irinjalakuda

External Examiner:

Place: Irinjalakuda

Date:05 /02/2022

2
 DECLARATION

I hereby declare that the project work entitled “SPECTRUM OF GRAPH” submitted to the
Christ College (Autonomous) in partial fulfillment of the requirement for the award of the B.Sc.
Degree programme in Mathematics is a record of original project work done by me during the
period of my study in the Department of Mathematics, Christ College (Autonomous),
Irinjalakuda.

Date :05-02-2022

Place: Irinjalakuda
SHAHMA SALIM-CCATSMT060

3
 ACKNOWLEDGEMENT

First, there are no words to adequately acknowledge the wonderful grace that my Redeemer has
given me. There are many individuals who have come together to make this project a reality. I
greatly appreciate the inspiration, support and guidance of all those people who have been
instrumental for making this project a success.
I express my deepest thanks to my guide Mrs. Akshara R, Adhoc Lecturer,
Department of Mathematics, Christ College (Autonomous), Irinjalakuda, who guided me
faithfully through this entire project. I have learned so much from her both in the subject and
otherwise. Without her advice, support and guidance, it find difficult to complete this work.
I take this opportunity to express my thanks to our beloved principal Fr.Dr.Jolly
Andrews CMI, who gave me the golden opportunity to do this wonderful project on the topic
“Spectrum of Graph".
I mark my word of gratitude to Dr. Joju K.T, HOD-in-Charge and all other teachers of
the department for providing me the necessary facilities to complete this project on time.
I want to especially thank all the faculty of the library for providing various facilities for
this project.
Words cannot express the love and support I have received from my parents, whose
encouragement has buoyed me up from the beginning till the end of this work.

Shahma Salim-CCATSMT060

4
 CONTENTS

1 INTRODUCTION 7

2 PRELIMINARIES 8
2.1 GRAPH THEORY . . . . . . . . . . . . . . . . . . . 8
2.1.1 Graph: . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2 Loop: . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Multiple edges (Parallel edges):. . . . . . . . . . . . . . . 8
2.1.4 Simple graphs (Strict graphs): . . . . . . . . . . . . 9
2.1.5 Complete Graph (Kn): . . . . . . . . . . . . . . . . 9
2.1.6 Degree of a vertex: . . . . . . . . . . . . . . 9
2.1.7 Cycle: . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.8 Acyclic graph: . . . . . . . . . . . . . . . . . . . . . 10
2.1.9 Subgraph: . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.10 Isomorphism: . . . . . . . . . . . . . . . . . . . . . 10
2.2 LINEAR ALGEBRA . . . . . . . . . . . . . . . . . . 11
2.2.1 Eigen value of a matrix:. . . . . . . . . . . . . 11
2.2.2 Characteristic polynomial: . . . . . . . . . . . . . . 11
2.2.3 Minimal polynomial: . . . . . . . . . . . . . . . . . 12
2.2.2 Monic polynomial: . . . . . . . . . . . . . . . . . . 12

3 ALGEBRAIC GRAPH THEORY 13

3.1 THE SPECTRUM OF A GRAPH . . . . . . . . . . . . 13
3.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.2 Definition . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.3 Result . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.4 The adjacency matrix of a bipartite graph . . . . . . . . . 14
3.1.5 Remark . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.6 Definition . . . . . . . . . . . . . . . . . . . . . . 15
3.1.7 Example . . . . . . . . . . . . . . . . . . . . . . . . 16

5
 3.1.8 Cospectral Graphs . . . . . . . . . . . . . . . . . . 16
3.1.9 Example . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.10 Remark . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 PRINCIPAL MINOR. . . . . . . . . . . . . . . . . . . . . 19
3.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 WALK IN A GRAPH . . . . . . . . . . . . . . . . . . . . 19
3.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.2 Lemma . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 CONNECTED GRAPHS. . . . . . . . . . . . . . . . . . . 19
3.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 19
3.5 REGULAR G R A P H S . . . . . . . . . . . . . . . . . . . . 20
3.5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 20
3.6 INCIDENCE MATRIX . . . . . . . . . . . . . . . . . . . . 20
3.6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 21
3.6.2 Definition . . . . . . . . . . . . . . . . . . . . . . . 22
3.6.3 Example . . . . . . . . . . . . . . . . . . . . . . . . 22
3.6.4 Definition . . . . . . . . . . . . . . . . . . . . . . . 23
3.6.5 Definition . . . . . . . . . . . . . . . . . . . . . . . 23
3.6.6 Example . . . . . . . . . . . . . . . . . . . . . . . . 23
3.6.7 Remark . . . . . . . . . . . . . . . . . . . . . . . . 23

4 CONCLUSION 25

5 BIBLIOGRAPHY 27

6
Chapter 1

INTRODUCTION

Graph theory is a branch of mathematics started by Euler as early as 1736.It took a

hundred years before the second important contribution of kirchhoff had been made for the
analysis of electric networks. Graphs dealt in graph theory and not of the variety with an
x- and y- axis, but rather are made up of vertices, usually represented as points, and edges,
usually thought of as lines between two vertices.

Algebraic graph theory can be viewed as an extension to graph theory in which

algebraic methods are applied to problems about graphs. It isconcerned with the use of
algebraic techniques in the study of graphs.

Spectral graph theory, as the main branch of algebraic graph theory, isthe study of
properties of graphs in relationship to the characteristic polynomial, eigenvalues and
eigenvectors of vectors of matrices associated with graphs, such as it adjacency matrix or
Laplacian matrix. Spectral graph theory emerged in the 1950 and 1960s.

A general graph Γ is a triple consisting of a vertex set VΓ edge set EΓ and a relation
that associates with each edge two vertices, not necessarily distinct, called its end points.

Here we deal with the applications of linear algebra and matrix theory to the study of
graphics. We begin by introducing the adjacency matrix of a graph. The adjacency
matrix and incidence matrix of a graph completely describes a graph. Thus we try to
deduce the relationship between a graph and the characteristic polynomial of its
adjacency matrix. We also deal with spectrum of a graph, principal minor, w a l k ,
connected graph and regular graphs.

7
Chapter 2

PRELIMINARIES

2.1 GRAPH THEORY

2.1.1 Graph:
A graph is a triple consisting of a vertex set VΓ, an edge set EΓ and a relation that
associates with each edge two vertices, not necessarily distinct, called its end points.

2.1.2 Loop:
An edge whose end points are equal is called a loop.

2.1.3 Multiple edges (Parallel edges):

Edges having same pair of end points are called multiple edges

8
 2.1.4 Simple graphs (Strict graphs):
A graph having no loops or multiple edges is called a simple graph.

2.1.5 Complete Graph (Kn):

A graph in which any two distinct vertices are adjacent is called a complete graph. A
complete graph with n-vertices is denoted as Kn

2.1.6 Degree of a vertex:

For a simple graph, degree of a vertex ν is the number of incident edges on ν. For a
graph containing it and twice the number of loops containing it.

2.1.7 Cycle:
A cycle is a graph with an equal number of vertices and edges whose vertices can be
placed around a circle so that two vertices are adjacent if and only if they appear
consecutively along the circle. A cycle with n vertices is denoted as Cn.

9
2.1.8 Acyclic graph

A graph without any cycles is called an acyclic graph.

2.1.9 Subgraph
H is a subgraph of a graph G if the collection of vertices and the collection of edges of
H, is a subset of the collection of vertices and collection of edges of G respectively and
the assignment of end points to edges in H is the same as in G.

10
2.1.10 Isomorphism:

An isomorphism from a simple graph Γ to a simple graph Γ ′ is a bijection f : V Γ →

V Γ ′ such that the edge uv ∈ EΓ if and only if the edge f (u)f (v) ∈ EΓ ′. if an

isomorphism exist between Γ and Γ ′ ,we say that Γ is isomorphic to Γ ′ , denoted as

Γ ∼= Γ ′.

2.2 LINEAR ALGEBRA

2.2.1 Eigen value of a matrix:

× matrix. A non zero vertex X is called a characteristic vector

Let A be a n×n square
of the matrix A, if there is a number λ such that AX = λX. then the number λ is
called the characteristic root or eigen value of A ,corresponding to the characteristic
vector X.

2.2.2 Characteristic polynomial:

In linear algebra, the characteristic polynomial which is invariant under matrix similarly
and has the eigen values as roots.

11
2.2.3 Minimal polynomial:
The minimal polynomial of a matrix is the monic polynomial of the smallest degree. It
divides the characteristic polynomial.

2.2.4 Monic polynomial:

In algebra ,a monic polynomial is a single variable polynomial in which the leading
coefficient ( the nonzero coefficient of highest degree) is equal to one.

Example: x2 + 3 is monic.

12
Chapter 3

ALGEBRAIC GRAPH THEORY

3.1 THE SPECTRUM OF A GRAPH

3.1.1 Definition :
Suppose that Γ is a graph whose vertex set V Γ is the set {v1, v2, ........................ , vn}
and consider EΓ as the set of all unordered pairs of element of V Γ .If {vi, vj}
is in EΓ ,when we say that vi and vj are adjacent.

3.1.2 Definition

The adjacency matrix of the graph Γ is the n × n matrix A = A(Γ )whose

entries aij are given by,

1;if vi and vj are adjacent0;

aij =
otherwise

3.1.3 Result

If A is the adjacency matrix of the graph Γ , then

(i) A is a real symmetric matrix

Proof :
A is a real matrix since the entries of A are either 0 or 1.

Also, aij = 1 ⇒ vi and vj are adjacent ⇒ aij = 1

Similarly, aij = 0 ⇒ vi and vj are not adjacent ⇒ aij= 0

⇒ matrix.
Hence A is a symmetric

13
(ii) Trace of A is zero.(Note that we consider only simple graphs in ourstudy)

Proof :
In a simple graph a vertex vi is not adjacent to itself.

Thus aii = 0 ∀ i =1,2,. ....... ,n

Hence, trace of A =⅀aij =0
i=1

3.1.4 The adjacency matrix of a bipartite graph

A graph Γ is called bipartite if its vertex set is the union of two disjoint independent
sets V1 and V2 called partite sets of Γ such that each edge has one vertex in V1 and the
other vertex in V2.

i.e. V Γ = V1 ∩ V2 =0

If we order the vertices so that those in V1 come first, then the adjacency matrix of a
bipartite graph takes the form

0 𝐵
A =[ ]
𝐵𝑡 0
For example, Consider the
V1 = {x,y,z,w}

V2 = {a,b,c,d}

V1 ∪ V2 = {x,y,z,w,a,b,c,d}

14
V1∩ = Φ

3.1.5 Remark
Suppose λ is an eigen value of A. Since A is real and symmetric, λ
is real and it can be deduced by solving the equation det (λI − A) = 0.

3.1.6 Definition
The spectrum of a graph Γ is the set of numbers which are eigen values of A(Γ )
together with their multiplicities. If the distinct eigen values of A(Γ ) are λ0 > λ1 >
..... > λs−1 , and their multiplicities are
m(λ0), m(λ1), ....., m(λs−1), then we shall write

λ0 λ1 λs −1
SpecΓ =( 𝑚(𝜆0) 𝑚(𝜆1)𝑚(𝜆𝑠−1)
)

15
3.1.7 Example
Consider the complete graph K4

0 1 1 1
1 0 1 1
Its adjacency matrix is given by A=[ ]
1 1 0 1
1 1 1 0

To find the eigen values of A , put det (A-λI) = 0.

The eigen values of A are -1 (multiplicity 3) and 3 (multiplicity 1)Therefore,
3 −1
Spec K 4 = ( )
1 3

3.1.8 Cospectral Graphs

Two non stop isomorphic graphs are said to be cospectral if they have the same eigen
values with the same multiplicity. (i.e they have the same spectrum).

16
 3.1.9 Example
0 1 0 1 0
1 0 1 0 0
Consider the graphs A(Γ)= 0 1 0 1 0
1 0 1 0 0
[0 0 0 0 0]

0 0 1 0 0
0 0 1 0 0
A = A(Γ1) = 1 1 0 1 1
0 0 1 0 0
[0 0 1 0 0]

det (A − λI) = det (A1 − λI) = −λ5 + 4λ3

So the eigen values of A and A1 are 0(multiplicity 3),

-2and 2 (multiplicity 1)

Therefore,
2 0 −2
Spec Γ = Spec Γ1 =( )
1 3 1

17
3.1.10 Remark
We usually refer to the eigen values of A(Γ ) as the eigen values of the graphs Γ .The
characteristic polynomial det (A- χI) will be refer to as −
the characteristic polynomial
of the graph Γ and denoted by χ(Γ, χ).

If χ(Γ, λ) = λn + c1λn−1 + c2λn−2 + c3λn-3+ .... + cn denotes the characteristic

polynomial of Γ , then c1 = 0

Proof :

Let r1, r2, ...r n be the distinct eigen values of the characteristic equation

λn + c1λn−1 + c2λn−2 + c3λn−3 + ...............+ cn ............... (1)

Then (λ − r1)(λ − r2) ............. (λ − rn)=0

⇒ λn − (r1 + r2 + .... + rn)λn−1 + .... + (−1) nr1r2 ....r n=0. .............................. (2)

Comparing (1) and (2), we get

−c1 = r1 + r2 + .... + rn = Sum of the eigen values ............................. (3)

But sum of eigen values = Trance of adjacency matrix A = 0. ............................. (4)

(3) and (4) ⇒ c1 = 0

18
3.2 PRINCIPAL MINOR

3.2.1 Definition
A Principal minor is the determinant of a sub matrix obtained by taking a subset
of the rows and the same subset of the columns.

3.3 WALK IN A GRAPH

3.3.1 Definition
A walk of length l in Γ ,from vi to vj is defined as the finite sequence of vertices of
Γ ,vi = u0, u1, ...., u1 = vj such that ut−1 and ut are adjacent for 1 ≤ t ≤ l.

3.3.2 Lemma

The number of walks of length l in Γ ,from vi to vj is the entry in the position (i,
j) of the matrix A 1.

3.4 CONNECTED GRAPHS

Definition
• A graph is said to be connected if each pair of vertices is joined by a
walk.

• The number of edges traversed in the shortest walk joining vi and

vj is called the distance between vi and vj in Γ and is denoted by
∂(vi, vj).

• The maximum value of the distance function in a connected graph Γ

19
 is called the diameter of Γ .

3.5 REGULAR GRAPHS

Definition
A graph is said to be regular of degree k (or k-regular) if each ofthe
vertices has degree k.

For example,

3.6 INCIDENCE MATRIX

let C be the field of complex numbers , and let X be any finite set.
Then the set V of all functions from X to C is a finite dimensional vector space with
the operation defined by,

If f : XC and g : XC are functions in V, then

(f + g)(x) = f (x) + g(x)

20
(αf )(x) = αf (x) ∀x ∈ X, α ∈ C

Let X = {a1 , a2 , ....., an }. Define f1 : XC ∀i = 1, 2, ....., n by

f1 (aj)= 1; if i=j
0; if i≠j

i.e.for a fixed i,

fi = (fi(a1), ....., fi(ai−1), fi(ai), fi(ai+1), .............. , fi(an))

=(0,......,0,1,0,......,0); where i occurs in the ith place.

Then {f1 , f2 , ......, fn } forms a basis for V and dim V = n = |X|

3.6.1 Definition
The vertex space C0(Γ ) of a graph Γ is the vector space of all functions from VΓ
to C.

Let V Γ = {v1, v2, ........ , vn}

Any function η : V Γ C can be represented by a column vector,

y = [y1, y2, ......, yn]T ; yi = η(vi), i = 1, 2, ........ , n

i.e. y = [η(v1), η(v2), ......, η(vn)]T = Im(η)

The edge space C1(Γ ) of a graph Γ is the vector space of all functions from EΓ
to c.

Let EΓ = {e1, e2, ......... , em}

Any function ξ : E ΓC can be represented by a column vector,

x = [x1, x2, ......, xm] T ; xi = ξ(ei), i = 1, 2, ....... , m

21
i.e. x = [ξ(e1), ξ(e2), ......, ξ(em)]T = Im(ξ)

1; ifi = j
B1 = {ε1, ε2, ......, εm} where εi(ej) =
0; if i ≠
= j

Forms a standard basis for C1(Γ ) and so dimension of C1(Γ ) ism.

3.6.2 Definition
Suppose that Γ has vertices V Γ = {v1, v2, ......, vn} and edges

EΓ = {e1, e2, ......, em}. Then we define the incidence matrix of order n×m,

X(Γ) as (X)ij= 1; If vi and ej are incident

0; Otherwise

3.6.3 Example
Consider the graph Γ :

Its incidence matrix is given by

1 1 0 0 0
0 0 1 1 0
0 0 0 0 1
1 0 1 0 0
[0 1 0 1 1]

22
 3.6.4 Definition
A graph Γ is said to have an orientation if for each edge eα = {vσ, vτ } of Γ we
shall chose one of vσ, vτ to be the positive end of eα and the other to be the negative end.

3.6.5 Definition

The incident matrix D of Γ , with respect to a given orientation of Γ, is the

n × m matrix (dij) whose entries are,

+1; if vi is the positive end of ej

dij = −1; if vi is the negative end of ej

0 ; otherwise

3.6.6 Example
Consider the graph Γ :

The incidence matrix D w.r.t the given orientation is given by,

−1 +1 0 0 0
0 0 +1 −1 0
0 0 0 0 +1
+1 0 −1 0 0
[ 0 −1 0 +1 −1]

23
3.6.7 Remark
• The rows of the incidence matrix correspond to the vertices of Γ and the
• column corr es pond to the edges of Γ.

• Each column contain just two non- zero entries +1 and -1, representing
the positive and negative ends of the corresponding edge.

24
 Chapter 4

CONCLUSION

The origin of the word graph appeared for the first time in 1878. In this project,

we have discussed some basic concept regarding the algebraic techniques in the study of

graphs. We dealt with the application of linear algebra and matrix theory in the study of

graphs and obtained certain general result pertaining to graphs.

Graph theory has application in several other sciences. The use of graph theory in

physics is today well established and gaining even more popularity after the recent

discovery of graphene, which is an allotrope of carbon which is much stronger than steel.

Graph theory has played a vital role in the study of its honey comb structure.

The most important area of research and education in the application of graph theory

is in physics and in electrical network designing. The relation between electrical network

and graph is very natural. A simple electrical network can be represented as a graph in

which vertices denote various devices and edges a s i ts connections.

One of the several and varied application of graph theory is found in Architecture and

Design. Graphs can be used, at least in two different stages of the design. On one hand, at

the initial process of design, inorder to draw an outline or to make a sketch of the project.

On the other hand, as an instrument of analysis of the performed project.

25
 Since the helical structure of DNA was proposed, many problems about this structure

were posed.

One of the important problems is how to read and recognize primary structure of a

DNA sequence. DNA fragment assembly is a newly explored method of determining

whether or not a reassembled strand of DNA, matches the original strand. One particular

way to perform this method is by using concepts from graph theory.

Graph theory also has applications in molecular chemistry and organic chemistry where

graphs are used to represent molecules. Graphical representation of large protein molecules

makes their study easy. Graph theory also has application in drug designing, genetics,

engineering, architecture and computer science

26
Chapter 5

BIBLIOGRAPHY

1. ALGEBRAIC GRAPH THEORY

- NORMAN BIGGS (Second Edition, Cambridge University press)

2. ALGEBRAIC GRAPH THEORY

-CHRIS GODSIL, GOFDON ROYLE (S p r in g er, New York )

3. LINEAR ALGEBRA
-KENNETH HOFFMAN, RAY KUNZE (S e c o n d edition, PH)

27