Some Algebraic Properties Of Bi-Cayley Graphs

Bi-Cayley graphs are a class of new defined graphs. The connectivity of Bi-Cayley has been studied in depth. In this thesis, we study the adjacency matrixof some Cayley digraphs and some algebraic properties of Bi-Cayley graphs: theeigenvalues, the number of spanning trees.In chapter one, we introduce the background and terminology. Chapter twois devoted to studying the adjacency matrix of some Cayley digraphs. For a finitegroup G and a subset S of G, the Cayley digraph D(G,S) is a graph with vertexset G and arc set {(x,sx)|x∈G,s∈S}. When S = S-1, D(G,S) corresponds toan undirected graph C(G,S), which is called a Cayley graph. When G is a cyclicgroup, the Cayley digraph is called a circulant digraph. A matrix A∈Cn×n issaid to be normal if A-A = AA-, where A- denotes the complex conjugate of thetranspose of A. In chapter two, we show that the adjacency matrix of a Cayleydigraph of abelian group is normal; when S is the union of a family of conjugacyclasses of G, the adjacency matrix of the Cayley digraph D(G,S) is normal.In chapter three, we study the relation between the eigenvalues of the di-rected Cayley graphs and Bi-Cayley graphs when the adjacency matrix of thedirected Cayley graph is normal. Let G be a finite group, S(possibly, containsthe identity element) be a subset of G. The Bi-Cayley graph BC(G,S) is abipartite graph with vertex set G×{0,1} and edge set {{(g,0),(gs,1)}, g∈G, s∈S}. When G is a cyclic group, the Bi-Cayley graph is also called Bi-Circulant graph. Letλ1,λ2,···,λn be the eigenvalues of the Cayley digraphD(G,S) whose adjacency matrix is normal, then the eigenvalues of BC(G,S) are±|λ1|,±|λ2|,···,±|λn|. Especially, we obtain the eigenvalues of Bi-Circulantgraph. Let S = {s1,s2,···,sk} be a subset of G.(1) If S = S-1, the eigenvalues of the Bi-Circulant graph BC(G,S) are±k,±|εs1j+εs2j +···+εskj|(j = 1,2,···,n - 1);(2) If S = S-1, the eigenvalues of the Bi-Circulant graph BC(G,S) are±k,±(εs1j+εs2j +···+εskj)(j = 1,2,···,n - 1). In chapter four, we study the number of spanning trees of Bi-Circulant graphs.Let G be a cyclic group of integers modulo n. Let S = {s1,s2,···,sk}(1≤s1