Paths, Cycles, and Spanning Subgraphs

路径、循环和跨越子图

• 批准号: 9970527
• 负责人: Xingxing Yu
• 金额: $ 8万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-01 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9970527&HistoricalAwards=false
• 关键词: Paths; Cycles; Spanning; Subgraphs

The investigator studies three types of problems in structural graph theory. (1) To determine if a given graph contains spanning subgraphs with small maximum degree, in particular, Hamilton cycles and spanning trees. (2) To determine if a given graph contains a specific graph as a topological minor. (3) To determine the number of cycles in a cycle decomposition or cycle covering of a graph. The invesitgator also works on the knapsack problem in combinatorial optimization. A graph can be viewed as a network which consists of nodes and links. Graph theory studies properties of networks (such as reliability) which are of both theoretical and practical interest. The investigator works on problems concerning the existence of small networks inside big networks. The research has potential applications in designing networks where special reliability condition is required at certain nodes.

研究者研究了结构图论中的三类问题。(1)确定给定图是否包含最小最大度的生成子图，特别是Hamilton环和生成树。(2)确定给定图是否包含一个特定图作为拓扑子图。(3)确定图的循环分解或循环覆盖中的循环数。本文还研究了组合优化中的背包问题。图可以看作是一个由节点和链接组成的网络。图论研究网络的特性（如可靠性），这既有理论意义又有实际意义。调查人员研究大网络中存在小网络的问题。该研究对某些节点有特殊可靠性要求的网络设计具有潜在的应用价值。