Embedded Files
Collaborators
Collaborators
Thomas Cameron
H. Tracy Hall
Michael Robertson*
Ben Small
Consider an unweighted directed graph (digraph) on n vertices. Setting w_{ij} = 1 if i → j is an edge and 0 otherwise, the Laplacian matrix is defined by equation (1).
In the (undirected) graph case, which is to say i → j if and only if j → i, the eigenvalues of the graph Laplacian have been used to characterize graphs and have applications to data mining, image processing, Markov chain mixing, chromatic numbers, and much more. There has been far less success in the study of the digraph spectra, however, mainly due to the asymmetry of the Laplacian. There are some results, but most consider the adjacency matrix or the symmetrized Laplacian.
A value which often appears in fundamental theorems about graphs is the algebraic connectivity, defined simply as the second smallest eigenvalue of the graph Laplacian. The spectrum of a digraph Laplacian is generally complex, though, so care must be taken. In Algebraic connectivity of directed graphs, Wu defines the algebraic connectivity of a digraph by (2), where e is the all ones vector. He shows this definition extends many fundamental theorems about graphs to digraphs, and it remains one of the most useful quantities related to a digraph.
Motivated in part by its close connection to Wu's algebraic connectivity, we developed in On the restricted numerical range of the Laplacian matrix for digraphs the novel notion of the restricted numerical range (RNR) of a digraph Laplacian, which we define as (3).
Notably, the RNR is a convex set in the complex plane whose minimum real part is equal to the algebraic connectivity. The definition is clearly also motivated by the usual numerical range, which is known to capture information about both the eigenvalues and eigenspaces of a matrix. Since L(e) = 0 for any digraph, the restriction can be viewed as removing unspecific information from the usual numerical range. The remaining information, read as shape of of the RNR, can be enough to fully characterize the digraph structure:
A digraph is a directed cycle if and only if its RNR is a polygon with vertices 1-exp(i2πj/n) for j = 1,...,n-1.
A digraph is a k-imploding star if and only if its RNR is the singleton {k}. No other singleton RNRs are possible.
A digraph is a directed join of two (undirected) graphs if and only if its RNR is a (necessarily real) line segment.
A digraph is a regular tournament digraph if and only if its RNR is a vertical line segment.
Many digraphs have the same spectrum as some of the digraphs listed above, underscoring what makes the RNR so powerful and exciting: the ability to characterize digraphs that are not characterized by their spectrum. Regarding the usual numerical range as a generalized spectrum, we suspect that all digraphs characterized by their spectrum are also characterized by their RNR, making the RNR a more robust tool for this purpose. We also suspect, though, that a proof of this result will be highly non-trivial.
Having characterized all degenerate polygonal RNRs (singletons and lines), in the sequel On digraphs with polygonal restricted numerical range we provide computational methods for finding polygonal digraphs and show that they can be partitioned into three classes:
First, the normal digraphs, meaning digraphs for which L itself is normal. We show that the disjoint union and the bidirectional join of two normal digraphs results in another normal digraph, and we provide an algorithm for constructing normal digraphs that are not such joins.
Second, the restricted-normal, meaning digraphs for which L is not normal but the restriction and projection of L in the RNR definition is normal. We show that the directed join of two normal digraphs results in a restricted-normal digraph, and that these are the only restricted-normal digraphs when the order is square-free or twice a square-free number. For all other orders we provide an algorithm for constructing restricted-normal digraphs which are not directed joins.
Lastly, the psuedo-normal digraphs, which are more elusive and technical to define. Essentially, this class consists of those digraphs for which the 'normal part' of the Laplacian is 'large enough' to mask its 'not normal part.'
Future research includes this class of pseudo-normal digraphs and the subclass of restricted-normal digraphs that are not directed joins, the aim being complete characterizations.
A non-polygonal digraph
A normal digraph
A restricted-normal digraph
A psuedo-normal digraph
Students:
I have several questions related to the above that are particularly well-suited for students looking forward to graduate degrees in mathematics or related fields, as this topic bridges the gap between tangible structural properties of graphs and abstract spectral properties of matrices. Some familiarity with linear algebra would be all that is required, as the digraph theory and other background could be learned as we go. If you have a strong interest in graph theory or matrix theory, I may have just the project for you!
Page updated
Google Sites
Report abuse