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

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

Theme 1. Difficult Combinatorial Search Problems The 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 Frameworks Graphs 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