Applying algebra to computing the clique number of a graph

应用代数计算图的团数

• 批准号: 1791058
• 金额: --
• 依托单位: Queen Mary University of London
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2016
• 资助国家: 英国
• 起止时间: 2016 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-1791058
• 关键词: Applying; algebra; computing; clique; number

A clique in a graph is a set of vertices with the property that every pair of distinct vertices in the set is joined by an edge, and the clique number of a graph is the size of a largest clique in that graph. Being able to determine the clique number of a graph has many applications, but is a computationally difficult problem. Algebra can be a big help in determining or bounding the clique number, including linear algebra and eigenvalue techniques, the clique adjacency polynomial for classes of graphs with certain regularity properties, and if the graph has nontrivial symmetries, group theory. The GRAPE package for the GAP system contains functions for the classification of cliques with given properties, and these are especially powerful for graphs with large groups of symmetries. As part of any project in this area, a student could start by computing an extensive catalogue of interesting graphs in GRAPE format for use in forming and testing conjectures and for testing new algorithmic ideas and programs. Such a library would be a tremendous resource both for the international algebraic graph theory community.

图中的一个集团是一组带有属性的顶点，该属性是集合中的每对不同顶点都与边缘连接在一起，并且图的集团数量是该图中最大的集团的大小。能够确定图的集团数量有许多应用程序，但在计算上是一个困难的问题。代数可以在确定或界限集团数字的方面有很大的帮助，包括线性代数和特征值技术，对于具有某些规律性属性的图形类别的集合邻接多项式，如果图形具有非平凡的对称性对称性，则组理论。 GAP系统的葡萄包包含具有给定特性的集团分类的函数，对于具有较大对称性组的图形，这些功能尤其强大。作为该领域任何项目的一部分，学生可以从计算葡萄格式的有趣图形目录开始，以用于形成和测试猜想，并测试新的算法思想和程序。对于国际代数图理论界来说，这样的库将是一个巨大的资源。

项目成果

The Smallest Strictly Neumaier Graph and its Generalisations

• DOI: 10.37236/8189
• 发表时间: 2018-09
• 期刊: Electron. J. Comb.
• 作者: R. J. Evans;S. Goryainov;Dmitry Panasenko