Difficult Combinatorial Search Problems and Graph Theory Models and Algorithms for Carbon Frameworks

主题1。图的着色问题以图G为输入，目的是给图G的顶点上色，使相邻的顶点颜色不同。这个问题是如此困难，以至于有一些相当小的图，这样找到一个最佳的着色要么太耗时，要么使用现有的算法是不可行的。我研究的一个目标是找到更快的图形着色算法。图着色问题有许多应用，包括确定无冲突调度、地图着色和寄存器分配。维恩图给出了有限集合之间所有可能的逻辑关系的图形表示。我们计划详尽地生成新的维恩图类。计算结果可用于研究关于维恩图的猜想。一个开放问题的例子是Winkler的猜想，即任何简单的维恩图都可以通过添加一条曲线扩展成一个更大的简单维恩图。（r, g）笼是一种具有最小顶点数的图，每个顶点的度数为r，最小循环大小为g。笼吸引了图论社区的很多兴趣，并且具有使其对网络拓扑具有吸引力的属性。有很多r和g的值，其中（r,g）笼的下界与已知最小的r-正则图的顶点数的上界之间存在很大的差距。我们的目的是试图关闭这些差距。主题2。碳框架的图论模型和算法图经常被化学家用作分子模型。本研究中考虑的分子具有碳框架。富勒烯对应于面尺寸为5或6的3规则平面图。虽然富勒烯是最近才被发现的（1985年），但由于其独特的化学性质和在材料科学、电子、纳米技术和医学方面的潜在应用，它们一直是研究的主题。苯类化合物是由熔融六边形环组成的不饱和分子。更普遍的是，多环芳烃（PAH’s）具有环尺寸为4,5,6和7的混合物。它们是自然产生的，是燃烧燃料产生的大气污染物，可能致癌。这项研究的目的是更好地了解这些分子的特性，如电流、稳定性、几何形状和共振能量。理解感应电流对于核磁共振解释化学特性是至关重要的。电流的图论模型通过给分子图的每条边一个方向和大小来表示电流。电流的图论模型比其他数值方法更容易实现，给出的答案也更简单。它们有助于预测无限分子族的电流。我们的目标之一是将当前模型相互比较，寻找不一致和异常。下一步是改进或重新开发基于图论的方法，使它们更准确地反映当前。迄今为止发表的图论方法更适合于通常相当平坦的苯类。我们计划开发扩展，以预测三维结构中的电流，例如富勒烯，或者图形没有完美匹配的情况，或者像多环芳烃那样循环大小变化的情况。进一步的研究将包括确定计算图不变量与所选分子性质之间的相关性。定义新的不变量太容易了，但是我们将识别那些有效计算的不变量，并提供与分子和扩展碳框架的几何和能量相关的信息内容

Theme 1. Difficult Combinatorial Search ProblemsThe graph coloring problem takes as input a graph G and the aim is to color the vertices of G so that adjacent vertices are different colors. This problem is so hard that there are some reasonably small graphs such that finding an optimal coloring is either overly time consuming or not feasible using existing algorithms. One goal of my research is to find faster graph coloring algorithms. The graph coloring problem has many applications including determination of conflict-free schedules, map coloring, and register allocation.Venn diagrams give pictorial representations of all possible logical relations between a finite collection of sets. We plan to exhaustively generate new classes of Venn diagrams. The computational results can be used to investigate conjectures about Venn diagrams. One example of an open question is Winkler's conjecture that any simple Venn diagram can be extended to a larger simple Venn diagram with the addition of a single curve.An (r, g)-cage is a graph having a minimum number of vertices such that each vertex has degree r and the minimum cycle size is g. Cages have attracted a lot of interest from the graph theory community and have properties that make them appealing for a network topology. There are many values for r and g where there is a large gap between the lower bounds given for an (r,g)-cage and the upper bound coming from the number of vertices in a smallest known existing r-regular graph of girth g. Our intent is to try to close those gaps. Theme 2. Graph Theory Models and Algorithms for Carbon FrameworksGraphs are often used by chemists as models for molecules. The molecules considered in this research have carbon frameworks. Fullerenes correspond to 3-regular planar graphs with face sizes 5 or 6. Although fullerenes were only recently discovered (1985) they have been the subject of intense research because of their unique chemistry and potential application in materials science, electronics, nanotechnology and medicine. Benzenoids are unsaturated molecules composed of fused hexagonal rings. More generally, polycyclic aromatic hydrocarbons (PAH's) have mixtures of ring sizes 4, 5, 6 and 7. They occur naturally and as atmospheric pollutants from burning fuels, and can be carcinogenic. The goal of this research is to better understand properties of these molecules such as currents, stability, geometry, and resonance energy. Understanding induced currents is critical for interpreting chemical characterisation by Nuclear Magnetic Resonance.Graph theory models for current represent current by giving a direction and magnitude to each edge of the molecular graph. Graph theory models for currents can be easier to implement and give a simpler representation of the answer than some other numerical approaches. They facilitate prediction of currents for infinite families of molecules. One of our goals is to compare current models to each other looking for inconsistencies and anomalies. The next step is to refine or redevelop the graph theory based methods so that they more accurately reflect the current. The graph theoretic approaches published so far are better suited to benzenoids which are often fairly flat. We plan to develop extensions for predicting current in 3D structures such as fullerenes, or cases where the graph has no perfect matchings or where the cycle sizes vary as for PAH's. Further research will involve determining correlations between computed graph invariants and chosen molecular properties. Definition of new invariants is all too easy, but we will identify those that are efficiently computable and offer information content related to geometry and energy of molecular and extended carbon frameworks