Graphs and digraphs

图和有向图

• 批准号: 170450-2008
• 负责人: Brown, Jason
• 金额: $ 1.75万
• 依托单位: Dalhousie University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2009
• 资助国家: 加拿大
• 起止时间: 2009-01-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=422780
• 关键词: Graphs; 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.

拟议研究的第一部分集中于组合多项式，从图着色到网络可靠性和独立多项式。代数和分析技术不仅用于限制无向和有向情况下的网络可靠性，而且还用于检查底层组合结构。定位多项式的根将更深入地了解基础系数的突出单峰性问题，并提供对与图和单纯复形中的独立性相关的新定义的分形类的更多见解。我计划继续研究强连通可靠性，这是有向图稳健性的有用衡量标准。特别是，有一个先前尚未研究过的相关新单纯复形，其属性可能有助于有效地限制这种可靠性度量。一种新方法将涉及首先使用适当的小波压缩有向图和无向图。