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

项目名称： 度条件和连通度条件下任意可分图的研究

项目编号： No.11501487

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 刘凤霞

作者单位： 新疆大学

项目金额： 18万元

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

中文关键词： 任意可分图；度数；连通性

英文摘要： 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.

英文关键词： Arbitrarily vertex decomposable graphs;Degree;Connectivity