Graphs and digraphs

点击翻译按钮获取中文摘要

The first part of the proposed research centers on combinatorial polynomials, from graph colourings to network reliability and independence polynomials. Algebraic and analytic techniques will be used to not only bound network reliability, both in the undirected and directed cases, but also to examine the underlying combinatorial structures. Locating the roots of the polynomials will shed more light on the outstanding unimodality problems of the underlying coefficients, as well as provide more insight into a newly defined class of fractals associated with independence in both graphs and simplicial complexes. I plan to continue to investigate strongly connected reliability, a useful measure of the robustness of a directed graph. In particular, there is an associated new simplicial complex that has not been previously studied, and its properties may help to efficiently bound this reliability measure. A new approach will involve compressing the directed and undirected graphs first with appropriate wavelets.