Paths, Cycles, and Spanning Subgraphs

研究人员研究了结构图论中的三类问题。(1)确定一个给定的图是否包含最大度小的生成子图，特别是哈密尔顿圈和生成树。(2)确定一个给定的图是否包含一个特定的图作为拓扑子图。(3)确定图的圈分解或圈覆盖的圈数。该算法还可用于解决组合优化中的背包问题。图可以看作是由节点和链路组成的网络。图论研究网络的性质(如可靠性)，这些性质既有理论意义，也有实际意义。这位研究人员致力于研究有关大网络中是否存在小网络的问题。该研究在对某些节点有特殊可靠性要求的网络设计中具有潜在的应用价值。

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.