Double covers of line graphs

Abstract

The concept of covering graphs is motivated by algebraic number fields and covering spaces in topology. Many researchers used covering of graphs in constructing Ramanujan graphs and in constructing pairs of cospectral but not isomorphic graphs. The present dissertation studies the double covers of line graphs and their properties. We have given a method to construct the double cover of a line graph with the help of the edge adjacency matrix of a graph and defined that graph as the symmetric edge graph. Many properties of symmetric edge graphs in relation to the factor graphs are studied. With the help of these double covers, we show that for any integer kand#8805;5, there exist two equienergetic graphs of order 2k that are not cospectral. It is shown that given a graph X, the symmetric edge graph of X is isomorphic to the Kronecker double cover of the line graph of X, denoted by and#120574;(X), if and only if X is bipartite. For a tree X, the diameter of and#120574;(X) is given. The family of trees X whose diameter is equal to the diameter of and#120574;(X) is obtained. Moreover, if X is a tree whose diameter is not equal to the diameter of and#120574;(X), then the diameter of and#120574;(X) is odd. We completely characterize the trees for which the algebraic connectivity of the Kronecker product of the line graph with the complete graph on m vertices, denoted by and#120573;and#119898; (X), is equal to m-1. The algebraic connectivity of and#120573;and#119898; (X), where X is a tree of diameter four is discussed. With the aid of the edge adjacency matrix, we defined the edge Laplacian matrix. Bipartite graphs can be characterized in terms of the spectrum of the edge Laplacian matrix. We computed the spectrum of the edge Laplacian matrix for the regular graphs, the complete bipartite graphs, the trees, and the unicyclic graphs. newline