The algebraic connectivity of graphs

Abstract

Algebraic graph theory is the study of how algebraic techniques can be used when working with graphs. The aim is to translate the properties of graphs into algebraic properties, and then use results and techniques in algebra to deduce and derive theorems about graphs. Of central importance in this topic are matrices that encode the structure of a graph. In particular, in this work we will be making extensive use of the adjacency matrix and the Laplacian matrix. Let G be a simple (with no loops or multiple edges) undirected graph having vertex set V (G) = {v1,v2,...,vn} and edge set E(G). The degree of a vertex v ∈ V (G), denoted by dG (v), is the number of edges of G incident to v. The 0−1 adjacency matrix A(G) = aij of G is the n×n matrix with aij =1 if vi is adjacent to vj and aij =0 otherwise. The n×n diagonal matrix D(G) is the matrix having the entries dG (v1),dG (v2),...,dG (vn) in this order on its leading diagonal and zero elsewhere. The matrix obtained by subtracting A(G) from D(G) is called the Laplacian matrix of G. It is known that L(G) is real and positive semidefinite, and thus its eigenvalues can be ordered as 0= λ1 ≤ λ2 ≤ ... ≤ λn Fiedler(1973)showed that the second smallest eigen value of L(G)is positive if and only if G is connected, and as a result α(G) = λ2 is called the algebraic connectivity of G. The investigation on this parameter is an important topic in algebraic graph theory and it has received much attention since it was introduced by Fiedler. A number of bounds for α(G) have been derived and the problem of determining those graphs that achieve the maximum or the minimum algebraic connectivity among given classes of graphs has been extensively studied. In the same seminal paper, Fiedler considered the relationship between the algebraic connectivity α(G), the vertex connectivity κ(G) of G, and the edge connectivity λ(G), where κ(G) and λ(G) are, respectively, the minimum number of vertices and edges that need to be deleted to disconnect G.

This has motivated other researchers to examine in more depth the relationship between the algebraic, the vertex and the edge connectivities. Others investigated the relationship between the algebraic connectivity and various graph invariants, such as the independence number and the matching number, and characterised those graphs that achieve some set bounds. In this dissertation we survey the existing literature on the algebraic connectivity of graphs. We present and analyse the main results on this parameter, give an extensive look at the algebraic connectivity of trees, and investigate therelationshipbetweenalgebraicconnectivity,vertexandedgeconnectivity, independence number and matching number. We then consider a particular family of graphs, namely the Generalised Petersen graphs, and present a conjecture concerning the algebraic connectivity of a particular subfamily of these graphs.