Spectra of Weighted Directed Graphs
No Thumbnail Available
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The study of mixed graph and its Laplacian matrix have gained quite a bit of interest among the researchers. Mixed graphs are very important for the study of graph theory as they provide a setup where one can have directed and undirected edges in the graph. In this thesis we present a more general structure than that of mixed graphs, namely the weighted directed graphs. We supply appropriate generalizations of several existing results in the literature for mixed graphs. We also prove many new combinatorial results relating the Laplacian (resp. adjacency) matrix and the graph structure. The notion of 3-colored digraphs is introduced here. This notion naturally generalizes the notion of mixed graphs but is much restricted in comparison to the weighted directed graph. Our main objective is to study the spectral properties of the adjacency and the Laplacian matrix of these graphs. We establish that the Laplacian matrix of weighted directed graphs are not always singular. A weighted directed graph is said to be singular (resp. non-singular) if its Laplacian matrix is singular (resp. non-singular). We give several characterizations of singularity of the weighted directed graphs. Apart from these, we provide some additional characterization of singularity of the connected 3-colored digraphs. A combinatorial description of the determinant of the Laplacian matrix of weighted directed graphs is supplied here. We prove that the adjacency (resp. Laplacian) spectrum of a 3-colored digraph can be realized as a subset of the adjacency (resp. Laplacian) spectrum of a suitable undirected graph. In order to achieve this some graph operations similar to that in [17] are introduced. Using these graph operations we show that for a connected 3-colored digraph on n vertices, there exists a mixed graph on 2n vertices whose adjacency and Laplacian eigenvalues are precisely those of the 3-colored digraph with multiplicities doubled. We also show that for a connected mixed graph G on n vertices, there is an unweighted undirected graph H on 2n vertices whose adjacency (resp. Laplacian) spectrum contains the adjacency (resp. Laplacian) spectrum of the mixed graph. Moreover, a description of the remaining adjacency (resp. Laplacian) eigenvalues of H is supplied. We observe that the graph H may be viewed as the result of a special case of a new graph operation on unweighted undirected graph introduced here. We show that the adjacency (resp. Laplacian) spectrum of the graph resulting from such an operation is completely determined by the adjacency (resp. Laplacian) spectra of some closely related weighted directed graphs. The Laplacian spectrum of the class of connected 3-colored digraphs containing exactly one non-singular cycle is studied here. Mainly, we study the smallest Laplacian eigenvalue and the corresponding eigenvectors of such graphs. We show that the smallest Laplacian eigenvalue of such a graph can be realized as the algebraic connectivity (second smallest Laplacian eigenvalue) of a suitable undirected graph. We determine the non-singular unicyclic 3-colored digraph on n vertices, which minimize the smallest Laplacian eigenvalue over all such graphs. A class of non-singular unicyclic 3-colored digraphs maximizing the smallest Laplacian eigenvalue over all such graphs is also supplied. We give a complete characterization of non-singular unicyclic 3-colored digraphs that have 1 as the second smallest Laplac...
Description
Supervisor: S. Poti
Keywords
MATHEMATICS