Spectra of Simple Graphs - Report

Spectra of Simple Graphs 1 Introduction Spectral graph theory concerns the connection and interplay between the subjects of graph theory and linear algebra. We assume that the reader is familiar with ideas from linear algebra and assume limited knowledge in graph theory. In this paper we begin by introducing basic graph theory terminology. Then we introduce the adjacency and laplacian matrices and explore the spectra of some basic types of graphs. Next, we look at the relationship between spectra, cliques and colorings of graphs. The paper concludes with a discussion on regular graphs and algebraic connectivity. 2 Preliminaries In section 2.1 we present some of the fundamental definitions from graph theory and introduce the adjacency matrix. Next, in section 2.2 we define and show some basic types of graphs and give the corresponding adjacency matrices. In sections 2.3 and 2.4 we discuss some of the basic algebraic principles necessary for comprehension of the paper and introduce the laplacian matrix. 2.1 Basic Graph Theory Definition 2.1. A graph, G, is defined by a set of vertices, V , and a set of edges, E, where each edge is an unordered pair of vertices. • G = (V, E) • E ⊆V ×V 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 vij ∈ E. vij represents the edge between vi and vj . Consequently, we say that vi and vj , are not adjacent if vij 6∈ E. A loop is an edge that is incident with the same vertex twice. Therefore in a simple graph, for ∀i, vii 6∈ E. Multiple edges occur when there are two or more distinct edges between the same two vertices. Unless otherwise stated, in this paper we will only consider simple graphs. A simple graph is a graph that contains no loops or multiple edges. Definition 2.2. The order of a graph, |G|, is the size of the set of vertices, |V |. For example, the graph below, G1 , has an order of 4. |G1 | = 4. 3 4 1 2 1 G1 has two edges: v12 and v23 where v12 = v21 and v23 = v32 . Because we are working with simple graphs, all edges have no direction associated with them. Therefore the order of the vertices in a edge is arbitrary because vij = vji for ∀ i, j. Definition 2.3. The degree of a vertex, deg(v) is the number of edges that are incident with the vertex. For G1 , deg(v1 ) = 1, deg(v2 ) = 2, deg(v3 ) = 1, and deg(v1 ) = 0. We call a vertex of degree zero an isolated vertex and a vertex of degree 1 a pendant vertex. Definition 2.4. A walk in a graph is a sequence of alternating vertices and edges that starts and ends at a vertex. A walk of length n is a walk with n edges. Consecutive vertices in the sequence must be connected by an edge in the graph. Definition 2.5. A closed walk is a sequence of alternating vertices and edges that starts and ends at the same vertex. Definition 2.6. A cycle is a closed walk which contains any edge at most one time. Definition 2.7. A graph is connected if there exists a walk of length k, 1 ≤ k ≤ n − 1, between any two independent vertices. In essence, in a connected graph we can move along edges to get from any vertex to any other vertex. Assume that G is connected and has a finite number of vertices. Therefore there is a walk of finite length between any two vertices i and j. Definition 2.8. The diameter of a graph, G, is equal to the greatest distance between any two vertices in the graph. The pictorial representation of a graph contains all necessary information needed to describe a particular graph. But, we can also represent a graph in the form of a matrix. Definition 2.9. The adjacency matrix, A, is an n × n matrix where n = |G| that represents which vertices are connected by an edge. If vertex i and vertex j are adjacent then aij = 1. If vertex i and vertex j are not adjacent then aij = 0. If G is a simple graph then aii = 0 for ∀i because there are no loops. Also, because simple implies undirected, aij = aji for ∀ i, j ∈ V . Theorem 2.1. The entries aij in Ak represent the number of walks of length k from vi to vj . We will proceed with a proof by induction on k. Proof. Let k = 1. From the definition of the adjacency matrix, we know that the entry aij of A1 is 1 if vertex i and j are connected. This gives the number of walks of length 1 between two vertices which will be 1 if the vertices are connected by and edge and 0 if they are not adjacent Assume that the aij entry of Ak gives the number of walks of length k from vertex i to j. From our assumption, all of the aij entries in Ak give the number of walks of length k from vertex i to vertex j. Row i in Ak is a row vector that represents the number of walks of length k from vertex i to every other vertex. Column j in A is a column vector that represents which vertices are adjacent to vertex j. Using matrix multiplication, the aij entries in Ak A are generated by multiplying the row vector i in Ak by the column vector j in A. Therefore Ak A is the summation of all walks of length k from vertex i to any vertex that is adjacent to vertex j. This is equivalent to the number of walks of length k + 1 from vertex i to vertex j. Therefore the aij entries in Ak represent the number of walks of length k from vi to vj . 2 Just previously, we showed that for the adjacency matrix, A, the aij entries in Ak represent the number of walks of length k between vertices i and j. Therefore the sum of the aij entry in A + A2 + A3 + · · · + An−1 equals the number of walks from vi to vj that are of length n − 1 or less. Note that the maximum diameter of a connected graph of order n is n − 1. Thus n−1 P Ak has positive k=1 integer entries for all aij if the graph is connected. Therefore we can find a walk of length n − 1 or less r P between any two vertices. The diameter of a graph G, is the minimum value of r such that Ak has k=1 positive entries for all aij . For complex graphs with a large number of vertices, finding the value of r will require much computation. We can use the matrix (A + I) to make the process of finding the value of r easier. Notice that (A + I)r = r P k=0 r k
Ar−k I k     r r r−1 =A + A I+ Ar−2 I 2 + · · · + I k 1 2     r r r r−1 =A + A + Ar−2 + · · · + I 1 2 r We can ignore the binomial coefficients because we are only concerned whether the values of aij are non-zero and we do not care about their exact integer value. Thus, the diameter of a graph, G is the minimum value of r such that (A + I)r has positive entries for aij ∀i, j. Corollary 2.1. Let B = (I + A). G is connected if and only if (B)n−1 has non zero entries in bij for ∀i, j. 2.2 Types of Graphs In this section we will introduce some of the common types of graphs which will appear throughout the paper. The graphs are a path, Pn , a cycle, Cn , a star, Sn , a complete graph, Kn , a bipartite graph, and a complete bipartite graph Kx,y . Path A path graph, Pn is a connected graph of n vertices where 2 vertices are pendant and the other n − 2 vertices are of degree 2. A path has n − 1 edges. Below is the graph P5 . 1 2 3 4 Figure 2.1 P5 The adjacency matrix of a path Pn is: APn  0 1  0   = 0  .. .  0 0 1 0 1 0 .. . 0 1 0 1 .. . 0 0 1 0 .. . ··· ··· ··· ··· .. . 0 0 0 0 0 0 ··· ··· where aij = 1 if |i − j| = 1 and aij = 0 otherwise. 3  0 0  0  0  ..  .  0 1 1 0 0 0 0 0 .. . 5 Cycle A cycle graph is a connected graph on n vertices where all vertices are of degree 2. A cycle graph can be created from a path graph by connecting the two pendant vertices in the path by an edge. A cycle has an equal number of vertices and edges. Below is the graph C4 . 4 1 3 2 Figure 2.2 C4 The adjacency matrix of a cycle graph Cn is:  0 1  0   AC n = 0  .. .  0 1 1 0 1 0 .. . 0 1 0 1 .. . 0 0 1 0 .. . ··· ··· ··· ··· .. . 0 0 0 0 0 0 ··· ···  1 0  0  0  ..  .  0 1 1 0 0 0 0 0 .. . where aij = 1 if |i − j| = 1 or (n − 1) and aij = 0 otherwise. Complete Graph A complete graph Kn is a connected graph on n vertices where all vertices are of degree n − 1. In other words, there is an edge between a vertex and every other vertex. A complete graph has n(n−1) edges. 2 Below is the graph K5 . 5 4 1 3 2 Figure 2.3 K4 The adjacency matrix of a complete graph Kn is:  0 1 1 0  1 1   AKn = 1 1  .. .. . .  1 1 1 1 1 1 0 1 .. . 1 1 1 0 .. . ··· ··· ··· ··· .. . 1 1 1 1 ··· ··· 4  1 1  1  1  ..  .  0 1 1 0 1 1 1 1 .. . where aij = 1 if |i − j| = 6 0 and aij = 0 otherwise. Bipartite Graph A bipartite graph is a graph on n vertices where the vertices are partitioned into two independent sets, V1 and V2 such that there are no edges between vertices in the same set. An example Bipartite graph on 6 vertices: 4 5 6 1 2 3 Figure 2.4 Bipartite Graph The general form for the adjacency matrix of a bipartite graph is:   O B A= BT O where B is x × y matrix in which |V1 | = x and |V2 | = y where x + y = n. Complete Bipartite Graph A complete bipartite graph Kx,y is a bipartite graph in which there is an edge between every vertex in V1 and every vertex in V2 . Below is the complete bipartite graph K3,3 . 4 5 6 1 2 3 Figure 2.5 K3,3 The general form for the adjacency matrix of a bipartite graph is:   O C AKx,y = CT O where C is the x × y matrix in which all entries are 1. Star A star graph, Sn , is a connected graph on n vertices where one vertex has degree n − 1 and the other n − 1 vertices have degree 1. A star graph is a special case of a complete bipartite graph in which one set has 1 vertex and the other set has n − 1 vertices. Sn = K1,n−1 . Below is the graph S5 . 5 3 1 2 5 4 Figure 2.6 S5 The adjacency matrix of a star graph Sn is:  0 1  1  ASn = 1   .. . 1 0 0 0 .. . 1 0 0 0 .. . ··· ··· ··· ··· .. . 1 0 0 0 .. .  1 0  0  0  ..  . 1 0 0 0 ··· 0 Note that aij = 1 if i or j is 1 but not when i = j and aij = 0 otherwise. 2.3 Laplacian Matrix Definition 2.10. The degree matrix, D, of a graph, G, is the diagonal matrix D = diag(d1 , d2 , . . . , dn ) where di is the degree of vertex i. Recall that the degree of a vertex is the number of edges that are incident with the vertex. Equivalently, the degree of vertex vi is the number of other vertices, vj i 6= j, that are adjacent to vi . For a simple graph, the maximum degree of any vertex, vi , is n − 1 where n is the number of vertices in the graph. If ∃i such that di = 0 then G is not connected. But, if for ∀i, di > 0 we cannot say for certain that G is connected. Below is an example graph and its corresponding degree matrix: 3 4 1 2   1 0 0 0 0 2 0 0   0 0 1 0 0 0 0 0 Below is an example of a graph and its corresponding degree matrix which is not connected, but for ∀i, di > 0. 3 4 1 2  1 0  0  0 0 0 2 0 0 0 0 0 1 0 0 5 0 0 0 1 0  0 0  0  0 1 Definition 2.11. For a simple graph, G, the laplacian matrix, L = D − A, where D is the degree matrix and A is the adjacency matrix. From our earlier definitions of D and A we see that aij ≥ 0 if i = j and aij ≤ 0 if i 6= j where aij are the entries of the laplacian matrix. 6 2.4 Spectrum In the previous section we showed how graphs can not only be represented as a picture but also be represented in matrix form. We now to introduce some ideas from linear algebra, as we will be working with matrices. In particular, we will introduce ideas that still relate to graphs. Definition 2.12. An eigenvalue is a root of the characteristic polynomial associated with a matrix. This set of all eigenvalues of the adjacency matrix is referred to as the adjacency spectrum of a graph. The set of all n eigenvalues of the n × n adjacency matrix is denoted as {λ1 , λ2 , . . . , λn } where λi ≥ λj for ∀i < j. Simularly, the set of eigenvalues of the laplacian martix is refered to as the laplacian spectrum of a graph. The set of all n eigenvalues of the n × n laplacian matrix is denoted as {ν1 , ν2 , . . . , νn } where νi ≥ νj for ∀i < j. Because both the adjacency and laplacian matrices are symmetric, we are guaranteed to only get real eigenvalues. Definition 2.13. The trace of a matrix is the sum of the entries along the main diagonal. Trace A = n P aii . i=1 From the definition of the adjacency matrix, aii = 0 for ∀i. For the laplacian matrix, aii = di for ∀i. n n P P Because traceA = λi and traceL = νi , we get the following equations for the eigenvalues of the i=1 i=1 adjacency and laplacian matrices. • trace(A) = n P λi = 0 i=1 • trace(L) = n P i=1 νi = n P di = i=1 e(G) 2 Let G be the graph of 4 vertices used earlier in this report. The pertinent matrices corresponding with this graph are: 3  1 0 D= 0 0 0 2 0 0 0 0 1 0 1   0 0 1 0 A= 0 0 0 0 4 1 0 1 0 0 1 0 0 2   0 1 −1 0 L= 0 0 0 0 −1 2 −1 0  0 0 −1 0  1 0 0 0 1 ν−2 1  0 1  ν−1 To find the eigenvalues of L we need to solve for ν in the equation:  ν−1  1 det  0 0 1 ν−2 1 0 det(νI − L) = 0   0 0 ν−1  1 0  1 = ν × det ν − 1 0 0 0 ν The eigenvalues of the laplacian matrix are√{ν1 , ν2 , ν3 , ν4 } = {3, 1, 0, 0} and the eigenvalues of the adja√ cency matrix are {λ1 , λ2 , λ3 , λ4 } = { 2, 0, 0, − 2}. In summary, the eigenvalues of the adjacency matrix are denoted λi whereas the eigenvalues of the laplacian matrix are denoted νi . 7 3 Spectra of Basic Graphs In this section we present the spectra of some basic graphs. We find the spectrum of star, path, and complete graphs, and state the spectra of cycles and complete bipartite graphs. 3.1 Star Sn Our goal is to find a recurrence relationship between the characteristic polynomials of star graphs.   λ −1 −1 −1 · · · −1 −1 λ 0 0 ··· 0   −1 0 λ 0 ··· 0   (λI − ASn ) = −1 0  0 λ ···    .. .. .. .. . .. ..    . . . . . −1 0 0 0 ··· λ Using cofactor expansion along the second row we get: det(λI − ASn ) = −a21 C21 + a22 C22 We see that a21 = −1, a22 = λ. C22 is the determinant of the matrix AS(n−1) and C21 is the determinant of the matrix:   −1 −1 −1 · · · −1 0 λ 0 ··· 0   0 0 λ · · · 0 B=   .. .. .. ..  ..  . . . . .  0 0 0 ··· λ Using cofactor expansion of B along the first column we get that: det B = −1C11 . C11 = det λIn−2 where In−2 is the n − 2 identity matrix. Thus det B = −λn−2 . Therefore: det(λI − ASn ) = −(−1)(−λn−2 ) + λ det(λI − AS(n−1) ) = λ det(λI − AS(n−1) ) − λn−2 Letting Fn be the characteristic equation of (λI − ASn ) we get the follow recurrence relationship. Fn = λFn−1 − λn−2 (eq. 3.1) We want an equation for Fn in terms of only λ. We now want to see what happens when we substitute Fn−1 = λFn−2 − λn−3 and then Fn−2 = λFn−3 − λn−4 into eq. 3.1. Fn = λFn−1 − λn−2 = λ(λFn−2 − λn−3 ) − λn−2 = λ2 Fn−2 − λn−2 − λn−2 = λ2 Fn−2 − 2λn−2 = λ2 (λFn−3 − λn−4 ) − 2λn−2 = λ3 Fn−3 − 3λn−2 8 We see that Fn = λk Fn−k − kλn−2 for k = {1, 2, 3}. In order to determine if it holds for ∀k < n, we assume that Fn = λk Fn−k − kλn−2 for ∀k < n. Proof. We will see if our previous assumption holds under the principle of mathematical induction. Letting k=0: Fn = λk Fn−k − kλn−2 = λ0 Fn−0 − 0λn−2 = Fn Assume that Fn = λk Fn−k − kλn−2 for ∀ k < n Therefore Fn = λk Fn−k − kλn−2 from our assumption and Fn−k = λFn−k−1 − λn−k−2 from our recurrence relationship. Fn = λk Fn−k − kλn−2 = λk (λFn−k−1 − λn−k−2 ) − kλn−2 = λk+1 Fn−k−1 − λn−2 − kλn−2 = λk+1 Fn−k−1 − (k + 1)λn−2 Therefore Fn = λk Fn−k − kλn−2 for ∀ k < n. Let k = n − 3. We now need to find the value of F3 . λ (λI − AS3 ) = −1 −1 Thus: −1 λ 0 −1 0 λ F3 = λ(λ2 ) + 1(−λ) − 1(λ) = λ3 − 2λ Finally, letting k = n − 3 and F3 = λ3 − 2λ we get: Fn = λk Fn−k − kλn−2 = λn−3 Fn−(n−3) − (n − 3)λn−2 = λn−3 F3 − (n − 3)λn−2 = λn−3 (λ3 − 2λ) − (n − 3)λn−2 = λn − 2λn−2 − nλn−2 + 3λn−2 = λn−2 (λ2 − (n − 1)) Letting Fn =0 we get the following values for λ: √ √ Adjacency Spectrum Sn = { n − 1, 0, 0, . . . , 0, 0, − n − 1} Where λ = 0 has multiplicity n − 2. For a spectrum that has repeated eigenvalues, we write the multiplicies as the exponent of the eigenvalue. √ √ Adjacency Spectrum Sn = { n − 1, 0n−2 , − n − 1} 9 3.2 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 Pn is:  0 1 0 0 1 0 1 0  0 1 0 1   APn = 0 0 1 0  .. .. .. .. . . . .  0 0 0 0 0 0 0 0  0 0  0  0  ..  .  0 1 1 0 ··· ··· ··· ··· .. . 0 0 0 0 .. . ··· ··· where aij = 1 if |i − j| = 1 and aij = 0 otherwise. To find the eigenvalues of the adjacency matrix we must first find the AP n .  λ −1 0 0 ··· 0 −1 λ −1 0 · · · 0   0 −1 λ −1 · · · 0  0 0 −1 λ · · · 0 (λI − APn ) =   .. .. .. .. .. . ..  . . . . .  0 0 0 0 ··· λ 0 0 0 0 · · · −1 characteristic equation of matrix 0 0 0 0 .. .           −1 λ Using cofactor expansion along the first column we get: det(λI − APn ) = λC11 − (−1)C21  λ −1   det(λI − APn ) = λ × det  0  ..  . 0 −1 λ −1 .. . 0 −1 λ .. . ··· ··· ··· .. .   0 −1 0 0    0  − (−1) × det  0  .. ..   . . 0 0 ··· λ 0 Taking a look at  −1 0  0  det  0   ..  .  0 0  0    ..  . λ −1 λ −1 0 .. . 0 −1 λ −1 .. . 0 0 −1 0 .. . ··· ··· ··· ··· .. . 0 0 0 ··· λ −1  0  (−1) × det  0   ..  . −1 λ −1 0 .. . 0 −1 λ −1 .. . 0 0 −1 0 .. . ··· ··· ··· ··· .. . 0 0 0 ··· 0 we see that this is equal to:  0 where this matrix is λI − APn−2 . Thus: 10  0 0  0    ..  . λ −1 λ −1 .. . 0 −1 λ .. . ··· ··· ··· .. .  0 0  0  ..  . 0 0 ··· λ det(λI − A) = λ det(λI − APn−1 ) − det(λI − AP n−2 ) Let fk be the characteristic polynomial of det(λI − APk ) Thus: fk = λfk−1 − fk−2 (eq. 3.2) In this paper we do not show how to get the spectrum of a path graph from eq. 3.2 and instead give the result from Godsil and Royle [5]. A Spectrum Pn = 2cos( πj ) j = {1, 2, . . . , n} n+1 Now we give some examples of the spectrum of certain path graphs. For P1 , the matrix (λI − AP1 ) is a 1 by 1 matrix with λ as the only entry. Therefore f1 =λ and the adjacency spectrum is {0}.   λ −1 For P2 , the matrix (λI − AP2 ) is Therefore f2 = λ2 − 1 and the adjacency spectrum is {1, −1} −1 λ   λ −1 0 For P3 , the matrix (λI − AP3 ) is −1 λ −1 Therefore f3 = λ3 − 2λ and the adjacency spectrum 0 −1 λ √ √ is { 2, 0, − 2}. 3.3 Complete Graph Kn To find the spectrum of a complete graph we use the idea of complements. Definition 3.1. The complement, Ḡ, of a graph, G, has the same vertex set as G and vi and vj are adjacent in Ḡ if and only if they are not adjacent in G. Below is the graph K5 and its complement K̄5 . 5 4 1 5 3 4 1 3 2 2 K5 K̄5 We will use the following formula and the idea of complements to find the general formula for the spectra of complete graphs. Theorem 3.1 [4]. If G is a regular graph of degree r with n vertices, then PḠ (x) = (−1)n x−n+r+1 PG (−x − 1) x+r+1 11 PḠ is the characteristic polynomial of the complement of the graph G. The complement of a complete graph Kn is a graph of n isolated vertices. Because Kn denotes a complete graph, let K¯n denote the complement of a complete graph on n vertices. The adjacency matrix of K¯n is:   0 0 0 0 ··· 0 0 0 0 0 · · · 0   0 0 0 0 · · · 0   AK¯n = 0 0 0 0 · · · 0    .. .. .. .. . . . . . . . . ..  0 0 0 0 ··· 0 which in an n by n matrix with all zeros. Thus, the characteristic polynomial of the complement of Kn is fn = λn and the adjacency spectrum is {0n }. Let fḠ (x) be the characteristic equation of Kn and fG be the characteristic equation of the complement of Kn . x−n+r+1 fG (−x − 1) x+r+1 x−n+r+1 fKn (x) = (−1)n fK¯n (−x − 1) x+r+1 x−n+1 = (−1)n fK¯n (−x − 1) x+1 x−n+1 = fK¯n (x + 1) x+1 x−n+1 = (x + 1)n x+1 = (x − n + 1)(x + 1)n−1 fḠ (x) = (−1)n Therefore the spectrum of a complete graph Kn is given by the roots of the equation: fKn (x) = (x − n + 1)(x + 1)n−1 Adjacency spectrum of Kn = {(n − 1)1 , −1n−1 } 3.4 Cycle Graph Cn and Complete Bipartite Graph Km,n For cycle graphs, Cn , their spectra are very simular to the spectra of path graphs. Godsil and Royle give that: Adjacency Spectrum Cn = 2cos( 2πj ) j = {0, 1, . . . , n − 1} n The smallest cycle is C3 so the above formula only holds for n ≥ 3. Recall that the general form for the adjacency matrix of a bipartite graph is:   O C AKx,y = CT O where C is the x × y matrix in which all entries are 1. From [4] we get that the spectra of complete bipartite graphs is given by: √ √ Adjacency Spectrum Kn,m = {− mn, 0n+m−2 , mn} 12 4 Cliques and Chromatic Number In this section we present additional ideas in graph theory which were not covered in the preliminaries. In particular, we focus on how eigenvalues and spectra relate to cliques and the chromatic number. In addition, we 4.1 Clique Counts Cliques are important in graph theory because they contain much information regarding the structure of graphs. Cliques are especially important in planar graphs and colorings of graphs. Definition 4.1. In a graph G, a clique is a subset of the vertices in the graph such that every vertex in the subset is adjacent with every other vertex in the subset. Because every vertex is adjacent to every other vertex, a clique is a complete subgraph. Define an i-clique as a clique with i vertices. A 1-clique contains only 1 vertex so the number of 1-cliques in any graph is equal to |G|. A 2-clique is a set of two vertices that are connected by an edge. Therefore the number of 2-cliques in a graph is equivalent to the number of edges in a graph, e(g). Definition 4.2. cl(G) is the clique number of a graph. This is equivalent to the largest complete sub-graph in the graph. If a graph is Kp+1 -free then it does not contain a sub-graph that is a complete graph of p + 1 vertices. For example, a graph that is K4 -free does not have a sub-graph that is K4 . It follows that the graph would also not have a sub graph Kj where j > n because then it would necessarily contain all complete graphs of order j and less. The following theorem given by V. Nikiforov in [3] relates the largest eigenvalue of the adjacency spectrum and the clique number. Theorem 4.1 [3]. If G is Kp+1 -free then r λ1 ≤ 2 p−1 e(g) p Even though cl(G) ≤ p, from [3] we get: s λ1 ≤ 2 cl(G) − 1 e(g) cl(G) If we can find the maximum eigenvalue of a graph then we can use the following inequality to find a lower bound for the clique number. This bound tells us that the graph contains at least one sub-graph for all complete graphs smaller than the lower bound for the clique number. s cl(G) − 1 λ1 ≤ 2 e(g) cl(G) cl(G) − 1 e(g) cl(G) λ21 cl(G) − 1 ≤ 2e(g) cl(G) λ21 1 ≤1− 2e(g) cl(G) 1 λ21 ≤1− cl(G) 2e(g) 1 ≤ cl(G) λ21 1 − 2e(g) λ21 ≤ 2 13 (eq. 4.1) 4.2 Maximum Clique of a Graph Because a clique is a complete subset of a graph, if |G| = n, then the following inequallity follows trivially: cl(G) ≤ |G| cl(G) ≤ n A graph of order n is necessarily Kn+1 free. It follows that: Corollary 4.1 [3]. If G is Kp+1 free then r λ1 ≤ 2 n−1 e(g) n Next we introduce Turáns theorm. Theorem 4.2 (Turáns Theorem)[5]. If G is Kp+1 free then e(g) ≤ p−1 2 n 2p Using Turáns theorem in conjuncture with theorem 4.1 we see that: r p−1 e(g) λ1 ≤ 2 p r p−1p−1 2 λ1 ≤ 2 n p 2p s 2 (p − 1) 2 λ1 ≤ n 2 p p−1 n λ1 ≤ p cl(G) − 1 λ1 ≤ n cl(G) n ≤ cl(G) n − λ1 (eq. 4.2) This inequality is similar to equation 4.1, but instead of using the number of edges it relies on the number of vertices. Taking the maximum of equation 4.1 and equation 4.2 will give the best lower bound for the clique number. For cases where the number of edges is unknown or too difficult to calculate, equation 4.2 is more useful. 4.3 Chromatic Number Definition 4.3. The chromatic number, χ(G), of a graph is the minimum number of colors necessary to color the vertices of a graph such that no vertices that are connected by an edge have the same color. If cl(G) is the size of the maximum clique of a graph then we need at minimum enough colors such that each vertex in the clique has a unique color. Thus cl(G) ≤ χ(G) Therefore λ1 ≤ χ(G) − 1 n χ(G) In [2] A.J. Hoffman gives the following inequality 14 Theorem 4.3. If λn is the least eigenvalue of G then: 1+ λ1 ≤ χ(G) ≤ 1 + λ1 λn Combining the two previous inequalities we get lower and upper bounds for χ(G) χ(G) − 1 ≤ λ1 ≤ 5 χ(G) − 1 n χ(G) Connectivity In this section we first introduce vertex and edge connectivity and then delve into algebraic connectivity. We show not only how spectra help determine the shape of a graph, but also how the eigenvalues associated with a graph give information that vertex and edge connectives do not provide. 5.1 Vertex and Edge Connectivity Definition 5.1 . The vertex connectivity, κ(G), of a graph, G, is the minimum number of vertices that need to be removed to disconnect the remaining vertices. Definition 5.2. The edge connectivity, (G), of a graph, G, is the number of edges that need to be removed to disconnect the vertices of the graph. Both the edge and vertex connectivities give a numerical answer regarding “how well connected” a graph is. In the Petersen graph, P , below (fig. 5.1), it is easy to see that the edge connectivity is 3 because we remove 3 edges incident with the same vertex to disconnect the graph. Similarly, the vertex connectivity is also 3 for the Petersen graph because to split the 10 vertices into 2 non-connected sets, we must remove at least 3 vertices which are all adjacent with a common vertex. The subsets of vertices or edges that when removed disconnect a graph are referred to as a vertex-cut and an edge-cut respectively. The size of the smallest vertex-cut and the smallest edge-cut are the vertex connectivity and edge connectivity of the graph. Figure 5.1. The Petersen Graph, P . Edge and vertex connectivities are useful values because they describe how “easily” a graph can be disconnected, but in some cases, they do not tell the entire story. For example take a look at the two graphs below, G5a and G5b . 15 3 2 7 8 6 9 7 8 6 9 5 1 4 Figure 5.2. G5a 3 2 5 1 4 Figure 5.3. G5b For both G5a and G5b , the edge and vertex connectivities are both one. (G5a ) = 1, (G5b ) = 1, κ(G5a ) = 1, and κ(G5b ) = 1. Intuitively, it seems that G5a is better connected than G5b because the two subsets of vertices {v1 , v2 , v3 , v4 } and {v6 , v7 , v8 , v9 } form complete graphs, K4 , in G5a , but only cycles, C4 in G5b . In other words, some of the subsets of vertices are more connected in G5a than in G5b , but as a whole, both graphs are assigned the same value for their edge and vertex connectivities. If we want connectivity to simply represent how easy it is the disconnect a graph, then vertex and edge connectives are sufficient. But, if we want connectivity to not only represent how easy a graph can be disconnected, but also represent the length of walks from some vertex vi to another vertex vj , then we need a new metric. Intuitively it seems that a graph that has shorter walks between vertices is more connected. To help with the problems of vertex and edge connectivities, we introduce algebraic connectivity, a(G), which not only takes into consideration edge and vertex connectivities, but also represents how connected vertices are in terms of the length of walks between them. 5.2 Algebraic Connectivity Definition 5.3 [4]. The algebraic connectivity, a(G), of a graph, G, is the value of νn−1 which is the second smallest eigenvalue in the laplacian spectrum of G. This definition explains the numerical value of algebraic connectivity, but it fails to explain exactly what algebraic connectivity means. Whereas the edge and vertex connectivities of a graph in essence focus on the least connected part of a graph, the algebraic connectivity can give a more overall picture of the connectivity of a graph. Algebraic connectivity is more concerned with the total number of vertices and how the edges connect them whereas vertex or edge connectivity is concerned with the smallest vertex or edge cut. We will see that graphs with a larger algebraic connectivity are usually more of a circular shape because in general the distance between vertices is small. For graphs with low algebraic connectivities, the graphs take on more of a path shape. For G5a and G5b the algebraic connectivities are: • a(G5a ) ≈ 0.2087 • a(G5b ) ≈ 0.1864 Therefore a(G5a ) > a(G5b ). In G5a the length of the walk from v1 to v9 is 4 whereas in G5b the length of the walk from v1 to v9 is 6. This will become more apparent when we discuss strongly regular graphs because they usually have the smallest diameter of all regular graphs. To better understand algebraic connectivity, it is useful to compare it with edge and vertex connectivity. First, we give an important lemma that relates the adjacency and laplacian matrices. 16 Theorem 5.1 [5]. Let X be a regular graph with valency k. If the adjacency matrix A has eigenvalues λ1 , λ2 , . . . , λn , then the Laplacian L has eigenvalues k − λn , k − λn−1 , . . . , k − λ1 . Thus: νi = k − λn−i+1 (eq. 5.1) Recall that λ2 is the second largest eigenvalue of the adjacency matrix and that νn−1 is the second least eigenvalue of the laplacian matrix. Therefore if we let i = n − 1: νi = k − λn−i+1 νn−1 = k − λn−(n−1)+1 νn−1 = k − λ2 (eq. 5.2) From definition 5.3 we have that a(G) = νn−1 . Substituting this into eq. 5.2 we get corollary 5.1 Corollary 5.1. If G is k-regular then a(G) = k − λ2 (G) The Petersen Graph is a 3-regular graph that is a strongly regular Moore graph with parameters (10, 3, 0, 1). Using MAPLE, we get the adjacency and laplacian spectrum of the Petersen Graph: Laplacian Spectrum = {0, 25 , 54 } Adjacency Spectrum = {−24 , 15 , 3} Therefore λ2 = 1 and νn−1 = 2. Because the Petersen graph is 3-regular we see that: a(G) = k − λ2 (G) νn−1 = 3 − λ2 (G) 2=3−1 2=2 This shows how eq. 5.2 works for the Petersen graph. If we are able to find either νn−1 or λ2 for a regular graph, we can find the algebraic connectivity. Let κ(G) represent the vertex-connectivity of a graph G. Recall that the vertex-connectivity is the size of the smallest vertex cut that makes the graph not connected. If G is a connected graph then νn−1 > 0 because the multiplicity of the zero eigenvalue of the laplacian is equivalent to the number of connected components in a graph. Corollary 5.2. If G is a k-regular graph, G is connected if and only if λ2 < k. Proof. Assume that a graph G is k-regular. From our initial discussion of the laplacian matrix we showed that the number of zero eigenvalues in the laplacian spectrum is equal to the number of connected components in a graph. A graph is connected if it has only one connected component. Therefore there can only be one zero eigenvalue in the laplacian spectrum and it follows that νn−1 > 0. From eq. 5.2 we have that if G is k-regular, νn−1 = k − λ2 . It follows that if νn−1 > 0 then k − λ2 > 0. Therefore we get that if G is k-regular, it is connected if and only if λ2 < k. It is a general rule that the algebraic connectivity determines to a degree the shape of a graph. Some of the most interesting results are from the comparisons of the algebraic connectivity of graphs all belonging to the same family of graphs. 17 It seems intuitive that a compete graph, Kn , is the most “well connected” possible simple graph. We showed in a previous week that the adjacency spectrum of a complete graph is {−1n−1 , (n − 1)1 }. Because a complete graph of n vertices is (n-1)-regular, from eq. 5.2 we have: a(G) = n − 1 − λ2 (G) = n − 1 − (−1) =n A complete graph has the greatest algebraic connectivity of any simple graph. There are no vertex cuts for a complete graph, so it is difficult to compare the vertex-connectivity and algebraic connectivity of a complete graph. The edge connectivity of a complete graph Kn is n − 1. 5.3 Algebraic Connectivity and Regular Graphs Below are two representations of 3-regular graphs on 10 vertices. 3 2 5 1 8 9 7 10 6 4 Figure 5.4. G5c Figure 5.1. The Petersen Graph, P . In section 5.1 we showed that the edge and vertex connectivities of the Petersen Graph are (P ) = 3 and κ(P ) = 3. For G5c which is shown in figure 5.4, (G5c ) = 1 and κ(G5c ) = 1. For G5c we can remove the edge incident with v5 and v6 to disconnect the graph. Also, we can remove either v5 or v6 to disconnect the graph. G5c , has a more path-like structure than the Petersen graph although both graphs are 3-regular graphs on 10 vertices. We will calculate the algebraic connectivity of the Petersen Graph from its adjacency matrix using Corollary 5.1 and the algebraic connectivity of G5c using MAPLE. Adjacency Spectrum Petersen Graph = {3, 15 , −24 } Therefore the algebraic connectivity of the Petersen graph, a(P ), is 2 and from MAPLE we get that the algebraic connectivity of G5c is ≈ 0.2215. 18 Next we will look at another 3-regular graph on 10 vertices that has vertex and edge connectivities of 2. All of the three previous graphs have been 3-regular graphs on 10 vertices, but their connectivities have varied greatly. Figure 5.5. G5d . For G5d the vertex, edge, and algebraic connectivities are: • κ(G5d ) = 2 • (G5d ) = 2 • a(G5d ) ≈ 0.5857 We get the follow results for the connectivities of the three 3-regular graphs on 10 vertices. Graph P G5d G5c κ 3 2 1  3 2 1 a 2 ≈ 0.5857 ≈ 0.2215 It turns out that G5c and the Petersen graph are the extreme examples for connectivity of 3-regular graphs on 10 vertices. Godsil and Royle [5] give that the 3-regular graphs, also known as cubic graphs, with minimum νn−1 on n ≡ 2 mod 4 vertices are of the form: Figure 5.6 and the 3-regular graphs with minimum νn−1 on n ≡ 0 mod 4 vertices are of the form: Figure 5.7 We now want to see how the algebraic connectivities of the graphs in figures 5.6 and 5.7 vary as we increase the number of vertices. We will refer to a graph on n vertices as 3Gn . 19 Graph 3G10 3G12 3G14 3G16 3G18 3G20 3G22 3G24 κ 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 a ≈ 0.2215 ≈ 0.1677 ≈ 0.1048 ≈ 0.0840 ≈ 0.0620 ≈ 0.0515 ≈ 0.0411 ≈ 0.0351 Ideally we would have more entries in the table for larger values of n, but it is difficult to make larger matrices in MAPLE. But, we do see a trend of decreasing algebraic connectivity as the number of vertices increases. We conjecture that there is an inverse relationship between the number of vertices and the algebraic connectivity for graphs of the same form. I am unsure if limn→+∞ a(Gn ) = 0 or if it converges to another number. The relationship between |G| and a(G) makes sense intuitively because algebraic connectivity takes into consideration the distance between vertices. For graphs of the forms in figure 5.6 and figure 5.7, as n increases, the distance between v1 and vn increases. Even though the vertex and edge connectivities remain the same, the algebraic connectivities decrease. For this reason, I believe that algebraic connectivity is a better metric of connectivity than edge or vertex connectivity because it delineates between graphs which have the same vertex and edge connectivities. 6 Conclusion In this paper we introduced some of the basic ideas from spectral graph theory, primarily focusing on finding the spectra of certain types of graphs and algebraic connectivity. With more time, the section on algebraic connectivity would have included a discussion on what happens when the number of vertices is very large. It appears that a path and other similar graphs will have an algebraic connectivity that approaches 0 as n gets very large whereas complete graphs will have an ever increasing algebraic connectivity as the order increases. 20