度条件和连通度条件下任意可分图的研究

Arbitrarily vertex decomposable graphs are modelling parallel systems, considered as networks connecting different computing resources. With this strong application background, studying the arbitrarily vertex decomposable graphs become a very active research field at present. In this project, we will uses the tools in graph theory and conbinatorial theory to investigate various properties of arbitrarily vertex decomposable graphs. In addition, since every graph with a hamilton path must be an arbitrarily vertex decomposable graph, by weakening some known conditions for the existence of hamilton path in a graph, such as degree sums condition and neighbourhood unions conditions, we estbalish some useful critirion for determing a graph to be arbitrarily decomposable. This will provide more abundant theoretical support for the design of parallel systems.

任意可分图是模拟于连接不同计算资源的平行系统的一类图，鉴于这个重要的应用背景，对任意可分图的研究是目前国际上非常活跃的研究领域。本项目将应用图论，组合论等工具，研究任意可分图的各方面性质。特别的，因为含有哈密尔顿路的图一定是任意可分图，本项目主要侧重于改进判定一个图有哈密尔顿路的条件，使其成为判定一个图是任意可分图的条件，特别是度和条件和领域并条件。这些研究将为平行系统的设计提供更丰富的理论支持。

2002年，Barth，Baudon 和 Puech 提出了任意可分图的定义。任意可分图是模拟于连接不同计算资源的平行系统（并行计算机，工作站的网络）的一类图，这种平行系统可同时被不同的应用程序使用，每个子系统被有效地分配给一个应用程序，且不同的应用程序间互不打扰。本项目主要研究各类图的任意可分性。我们得到了如下主要结果：刻画了树与圈的笛卡尔积图的任意可分性，以及毛毛虫树与圈的笛卡尔积图的任意可分性；证明了团数是2的不含两条边作为导出子图的图是任意可分图的充要条件是它有完美匹配或几乎完美匹配；证明了阈值图是任意可分图的充要条件是它有完美匹配或几乎完美匹配；刻画了不含两条边和四个顶点的圈作为导出子图的图是任意可分图的充要条件。