Svādhyāya - International Journal of Transdisciplinary Research and Development

(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

A Study in Algebraic Graph Theory

Jini J1, Hemalatha S2

Research Scholar1, Assisstant Professor2 , Department of Mathematics1,2,

Shrimathi Devkunvar Nanalal Bhatt Vaishnav College for Women2, Affiliated to University of Madras
jinigunaseelan@gmail.com1, hemalatha.s@[Link].in2

Abstract:
One of the important branches of Mathematics is Graph theory. In which algebraic methods applied to graph problems is
known as algebraic graph theory. A study in algebraic graph theory is carried out in this article and a new concept of Algebraic and
Geometric multiplicity to find the maximum matching of an undirected graph is introduced and discussed.
Key Words: Graph Theory, Matching, Maximum Matching, Geometric Multiplicity, complete graph, dense graph.
AMS Classification Key: 05C, 05C70, 911368, 15A18
1. Introduction:
One of the emerging branches of Mathematics is graph theory. In Graph theory the study of algebraic graph theory and its
application is one of the interesting area for researchers. Many research articles have been published and algebraic techniques is
increasingly used in graph structures. In this study, the concept of algebraic graph theory and its applications are highlighted.
2. Graph Theory:
In mathematics, the study of mathematical structures is graph theory which is used to model pair wise relations between
objects. A graph is made up of vertices (nodes) which are connected by edges (lines).
For example,

Konigsberg Bridge Graph

In the above figure the Konigsberg Bridge is converted to a graph, G= {V, E} where vertices V= {w, x, y, z} are the region on either side
of the river and edges E = {e1, e2, e3, e4, e5, e6, e7} are the path over the bridge.

The concept of graphs in Graph theory consists of some basic terms such as Degree of vertices, Adjacency matrix, Incidence
matrix, Path, Cycle, Walk , etc., and it also has some basic different types of graphs.
For example,

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 74
 Svādhyāya - International Journal of Transdisciplinary Research and Development
(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

3. Algebraic Graph theory:

Algebraic tools are used for elegant proofs in algebraic theory and there are many interesting algebraic objects associated
with graphs. Now there are more books dealing with various aspects of this subject. The books written by (N Biggs, 1993) and (Godsil
and Royle, 2001) in algebraic graph theory contains massive information. Here we study the research carried in algebraic graph theory
mainly Linear and Abstract algebra.
Some basic definitions and example are explained before studying in detail about algebraic graph theory.
An n x n matrix is said to be a symmetric matrix if the elements 𝑎𝑖𝑗 = 𝑎𝑗𝑖 or the transpose of matrix is the matrix itself, and
in graph theory the adjacency matrix of any undirected graph with or without self-loops is a symmetric matrix.
In graph theory the adjacency matrix is a square matrix of a finite graph whose components are expressed as 1 if the pair of
vertices of the graph is adjacent otherwise it is zero.
For example,

Undirected graph with self-loop Symmetric and adjacency matrix

The Eigen values of the adjacency matrix of a graph is known as the spectrum of graph.
For example, consider a complete graph with 3 vertices and 3 edges

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 75
 Svādhyāya - International Journal of Transdisciplinary Research and Development
(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

The characteristic polynomial of the adjacency matrix is,

𝜆3 − 3𝜆 − 2 = 0
𝜆 = −1, −1, 2 are the Eigen values of the graph and it’s the spectrum of graph.
The diagonal elements of a diagonal matrix in a graph theory is the degree of its vertices and it is known as the degree
matrix of the graph.
The Laplacian matrix in graph theory is formed by an undirected graph with no self-loops and multiple edges and it is given
as L = D – A, D is the degree matrix and A is the adjacency matrix of the graph.
For example, consider an undirected graph with 4 vertices and 6 edges

Adjacency matrix Degree matrix

The Laplacian matrix is given by,

The circulant graph in a graph theory is an undirected cyclic group of graph symmetries which takes any vertex to any other
vertex.
For example from (Rajasingh, 2013),

Algebra of graph is giving an algebraic structure to an undirected graph in graph theory and it has many uses in the field of
universal algebra.

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 76
 Svādhyāya - International Journal of Transdisciplinary Research and Development
(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

For example,
Consider a graph G whose vertices are positive integers and it is represented by a pair (V,E) where V is the set of vertices
and E subset of V x V is the set of edges. Then the algebraic structure is given by,
The structure (𝐺, +, →, 𝜀) introduced in the above satisfies the usual laws,
• 𝜀 is the empty set of the graph.
• (𝐺, +, 𝜀) is an idempotent commutative monoid.
• (𝐺, →, 𝜀) is a monoid.
• → distributive over +, (e.g.) 1 → (2+3) = (1 → 2) + (1 → 3)

3.1. Study of Graph theory using Linear Algebraic concept:

In modern presentations of geometry the fundamental is linear algebra including for defining basic objects like lines, planes
and rotations.

Algebraic graph theory in linear algebra is the study of the spectrum of adjacency matrix or the Laplacian matrix known as
spectral graph theory is the first branch of algebraic graph theory which involves the study of graph in connection with linear algebra.
A diagonalizable matrix can be factorized to a canonical form which represents the matrix in terms of Eigen values and Eigen vectors
are known as its spectrum.

Spectral graph theory is the study of the properties of a graph in relation to its characteristic polynomial, Eigen values and
Eigen vectors of matrices associated with the graph. A real symmetric matrix is orthogonally diagonalizable and its Eigen values are
real algebraic integers.
The adjacency matrix of a finite simple graph is a (0-1) matrix with zeros on its diagonal and the matrix is symmetric if it is
an undirected graph. In spectral graph theory the relation between a graph and the Eigen value, Eigen vectors of its adjacency matrix
is studied.
Linear Algebra Applied to graph theory (Paul M Nguyen, 2017) is an application to linear algebra using graph theory and it
is a best method of studying traffic flow for its networking, Electronic circuits or delivery routes. To solve this problem various matrix
operations that are well –defined on the adjacency matrix is considered and established method for representing a graph
mathematically.
Graph theory and Linear algebra (Dylan, 2017) explains the relationships between graph theory associated with matrix
representations and the matrix properties found in linear algebra. It identifies certain unique properties of special classes of graphs
such as complete graphs and acyclic graphs and how their specialty in graph theory reflects in their matrix properties.
Thermodynamic characterization of networks using graph polynomials (Cheng Ye, 2015) is a representation of graph
structure based on a characteristic polynomial from the normalized Laplacian matrix show how the polynomial is linked to the
Boltzmann partition function of network. This allows to find a number of thermodynamic quantities for the network, including the

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 77
 Svādhyāya - International Journal of Transdisciplinary Research and Development
(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

average energy and entropy. Also these thermodynamic variables can be computed in terms of simple network characteristics, e.g.,
the total number of nodes and node degree statistics for nodes connected by edges. The resulting Thermodynamic characterization can
be applied to real-world time-varying networks representing complex systems in the financial and biological domains.
An algebraic Representation of Graphs and Applications to Graph Enumeration (Mestre, 2013) is a recursion formula to
generate all the equivalence classes of connected Graphs with coefficients given by the inverses of the orders of their groups of
Automorphisms. An algebraic graph representation is used to apply the result to the Enumeration of connected graphs, all of whose
biconnected components have the same number of vertices and edges. The proof uses Abel’s binomial theorem and generalizes
Dziobek’s induction proof of Cayley’s formula.
Matrices of zeros and ones with fixed row and column sum vector (Richard, 1980) it consist set of all m x n matrices of 0’s
and 1’s having ri1’s row i and sj1’s in column j has proved new results. The results can also be formulated in the set of bipartite graphs
with bipartition into m and n vertices having degree sequence R and S respectively. Also it can be formulated as a set of hyper graphs
with m vertices having degree sequence R and n edges whose cardinalities are given as S.
3.2. Study of Graph Theory in Abstract Algebra concept:
The study of algebraic structure is known as Group theory. Rings, Fields are well-known algebraic structures with some
additional operations and axioms.
Algebraic graph theory in group theory specially involves study of Automorphisms groups and geometric group theory such
as symmetric graphs, vertex –transitive, edge – transitive graphs etc. The study of group theory in algebraic graph theory is also related
to the symmetry property of spectrum which is seen in its adjacency matrix.
The symmetry form of a graph which is mapped onto itself while preserving edge- vertex connectivity is known as
Automorphism of a graph and it is defined for both directed and undirected graphs.
The study of finitely generated groups creating connection between algebraic properties of such groups and geometric
properties in which the group acts. Also finitely generated groups itself act as geometric objects is an important idea of geometric
graph theory.
Applications of Group Amalgams to algebraic graph theory (Ivanov, 1994) it deals with an example of sub group of
Automorphism group and a graph. The group act as s-transitively on the graph if it act transitively on the set of paths of length s in the
graph. This is proved as a theorem for 1-transitive group, s will be the largest integer such that subgroup acts s-transitively.
Some application of graph theory to finite groups (Edward A Bertram, 1982) has a theoretic result concerning the degree
sequence, Vertex colorings and Vertex independence number which are used to derive theorems about finite groups.
Review and application of group theory to molecular systems biology (Edward A Rietman, 2011) it provides a mathematical
idea to understand the boundary between living and non-living systems. In this group theory and abstract algebra is applied to
molecular systems biology.
4. Algebraic and Geometric Multiplicity of and Undirected Graph:

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 78
 Svādhyāya - International Journal of Transdisciplinary Research and Development
(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

Matching Theory is also one of the important branches of Graph theory in which the maximum cardinality of different types
of graphs in both directed and undirected have been studied and many researchers have proved different theorems.
The study of finding maximum matching of an undirected graph through algebraic theory based on its multiplicity of Eigen
values is a new concept. In algebraic theory the study of Linear Algebra involves the spectrum of its Adjacency is the first branch of
Algebraic graph.

This concept was studied by Yunyun Yang and Gang Xie for the research article “Maximum Matching of a Digraph Based
on the Largest Geometric Multiplicity” (Yunyun, 2016). The same concept was used to find maximum matching of an undirected
graph based on Geometric and Algebraic Multiplicity.

Let A be an n × n matrix with Eigen value λ. Then the algebraic multiplicity of λ is the number of times λ is repeated as a
root of the characteristic polynomial. The Geometric multiplicity does not require a new technique because it is the dimension of the
null space.
The algebraic multiplicity and geometric multiplicity of Eigen values can differ but the geometric multiplicity never exceed
algebraic multiplicity. Also if for every Eigen value of A, if the geometric multiplicity equals the algebraic multiplicity then A is said
to be diagonalizable.
Application of algebraic multiplicity in population is studied in the article (Xue-zhi Li, 2001), in that article the algebraic
multiplicity of complex Eigen values of population operator is discussed. It is proved that under condition the complex Eigen value of
this operator is atmost algebraic multiplicity 1 and it results in an asymptotic expansion of the solution of corresponding population
system.
4.1. Algebraic Multiplicity of an undirected complete graph:
If adjacency matrix of a complete graph with unit weight in the absence of Self- loops is of the form

The characteristic polynomial of the adjacency matrix is,

|𝜆𝐼𝑁 − 𝐴| = [𝜆 − (𝑁 − 1)](𝜆 + 1)𝑁−1
Then the Eigen values and the corresponding Algebraic multiplicities are, if 𝜆1 = 𝑁 − 1 𝑡ℎ𝑒𝑛 𝛿(𝜆1 ) = 1 and if
𝜆2 = −1 𝑡ℎ𝑒𝑛 𝛿(𝜆2 ) = 𝑁 − 1
𝑙

∴ ∑ 𝛿(𝜆𝑗 ) = 𝛿 (𝜆1 ) + 𝛿(𝜆2 ) = 1 + 𝑁 − 1 = 𝑁

𝑗=1

Therefore, all the nodes are matched nodes.

4.2. Geometric Multiplicity of an undirected Sparse Graph and Dense graph (Yuan, 2013):

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 79
 Svādhyāya - International Journal of Transdisciplinary Research and Development
(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

The geometric multiplicity is the number of linearly independent eigenvectors of Eigen values. For an undirected graph the
largest geometric multiplicity 𝜇(𝜆𝑗 ) of the Eigen value 𝜆𝑗 of 𝐴𝑗
𝜇(𝜆𝑗 ) = dim 𝑉𝜆𝑗 = 𝑁 − 𝑟𝑎𝑛𝑘 {𝜆𝑗 𝐼𝑁 − 𝐴}

Where 𝜆𝑗 (𝑗 = 1, 2, 3, … , 𝑁)represent the distinct Eigen values of 𝐴 and 𝐼𝑁 is the unit matrix with the same as 𝐴.
If an undirected graph is a sparse graph ((i.e.) the number of edges is much less than the possible number of edges) and if the
rows of the adjacency matrix are linearly independent the Eigen value𝜆𝑗 = 0 (𝑗 = 1, 2, 3, … , 𝑁). Then the Geometric
Multiplicity 𝜇(𝜆𝑗 ) = 0. This gives that all the nodes of the graph is perfectly matched and the corresponding edges are perfectly
matched. Since the maximum matching based on geometric multiplicity gives the number of unmatched nodes.
If an undirected graph is a Dense graph ((i.e.) the number of edges is near to the possible number of edges) then
det(𝜆𝑚 𝐼𝑁 − 𝐴) = 0 if 𝜆 = −1 and it is the Eigen value of Largest Geometric Multiplicity.
Then column transformation is performed to the matrix (𝜆𝑚 𝐼𝑁 − 𝐴) to obtain column canonical and the linearly independent
rows are combined with linearly dependent rows to form a new matrix which gives the matched nodes and the corresponding matched
edges.

4.3. Perfect Matching of Bridge Graph based on Geometric and Algebraic Multiplicity (Jini.J, 2020)
A cubic undirected bridge graph is perfectly matched if 𝑛𝑖 - Bridges (i=1, 2, 3… n) are connected in a single path. For an
undirected cubic graph with zero bridge the perfect matching is based on Algebraic multiplicity and for 𝑛𝑖 - Bridges the perfect
matching is based on Geometric multiplicity. In this paper an undirected cubic graph connected in a single path has been found up to
3 bridges and the concept is extended to 𝑛𝑖 - Bridges.

4.4. A new definition of geometric multiplicity of eigenvalues of tensors and some results based on it (Li, 2015)
A new definition of geometric multiplicity of eigenvalues of tensors, and based on this and the study of geometric and
algebraic multiplicity of irreducible tensors’ eigenvalues gives a result that the eigenvalues with modulus have the same geometric
multiplicity. Also it has been proved that two-dimensional nonnegative tensors’ geometric multiplicity of eigenvalues is equal to
algebraic multiplicity of eigenvalues.

5. Conclusion:

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 80
 Svādhyāya - International Journal of Transdisciplinary Research and Development
(SIJTRD)

VOLUME-1 ISSUE-1 MAY 2021

In this paper, literature survey is made for the study of algebraic theory in Graph theory by the definitions and uses of first
three branches of Algebraic theory. Also some research articles based on algebraic theory was studied to perform further research in
the field of algebraic Graph theory. Finally my research in algebraic graph theory for finding maximum matching of an undirected
graph based on algebraic and Geometric multiplicity is explained briefly.

References:

Biggs.N, (1993) “Algebraic Graph Theory (2nd ed.)”, Cambridge: Cambridge University Press.

Paul [Link] and Liem Doan, (2017) “Linear Algebra Applied to Graph Theory”.

Dylan Johnson, (May 3, 2017) “Graph Theory and Linear Algebra”, May 3, 2017.

Cheng Ye, Cesar [Link], Thomas [Link], Filipi N. Silva, Francisco A. Rodrigues, Luciano da [Link], Andrea Torsello,
Edwin [Link], (2015) “Thermodynamic Characterization of Networks using graph Polynomials”, Physical Review 92, 032810.

Angela Mestre, 2013, “An Algebraic Representation of Graphs and Applications to Graph Enumeration”, Hindawi Publishing
Corporation, International Journal of Combinatorics, Volume 2013, Article ID 347613.

Chris Godsil, Gordon Royle, (2001) “Algebraic graph theory”, Springer International Edition.

Ivanov.A.A, Shpectorov.S.V, (1994) “Applications of group amalgams to algebraic graph theory”, Springer, Dordrecht, Vol 84.

Edward A. Bertram, (10 March, 1982) “Some Application of graph theory to finite groups”, North Holland Publishing company.

Edward. A .Rietman, Robert L Karp, Jack A Tuszynski, (2011) “Review and application of Group theory to molecular systems
Biology” Theoretical Biology and Medical Modelling.

Xue-zhi Li, Geni Gupur, Chun-Lei Tang, Guang-Tian Zhu, (2001) “The algebraic multiplicity of the complex eigen values of
Population operator and its application”, Applicable Analysis, International journal, Volume 80, Issue 3-4.

Yunyun Yang and Gang Xie, (2016) “Maximum Matchings of a Digraph Based on the Largest Geometric Multiplicity”, Hindawi
Publishing Corporation, Vol 2016, Article ID 4702387.

Jini J, Hemalatha S, (2020) “Perfect Matching of Bridge Graph based on Geometric and Algebraic Multiplicity”, Journal of Xidian
University”, ISSN NO: 1001-2400, Volume 14, ISSUE 11.

Z. Z. Yuan, C. Zhao, Z. R. Di, W.-X. Wang, and Y.-C. Lai, (2013) “Exact controllability of complex Networks,” Nature
Communications, vol. 4, article 2447.

Rajasingh, Indra & Manuel, Paul & Arockiaraj, Micheal & Rajan, Bharati. (2013). “Embedding of circulant networks” Journal of
Combinatorial Optimization. 26. 10.1007/s10878-011-9443-x.

Richard A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra and its Applications,
Volume 33, 1980, Pages 159-231, ISSN 0024-3795, [Link] (80)90105-6.

Li, Yiyong & Yang, Qingzhi & Yang, Yuning. (2015). A new definition of geometric multiplicity of eigenvalues of Tensors and some
results based on it. Frontiers of Mathematics in China. 10. 10.1007/s11464-015-0412-z.

© 2021, SIJTRD, ShrimathiDevkunvarNanalal Bhatt College for women, All right reserved [Link] 81