Paths, Cycles, and Spanning Subgraphs

研究者研究了结构图论中的三种类型的问题。(1)判定给定图是否包含最大度小的生成子图，特别是汉密尔顿圈和生成树。(2)确定给定图是否包含特定图作为拓扑子图。 (3)确定图的圈分解或圈覆盖中的圈数。invesitator还在组合优化中的背包问题。一个图可以被看作是一个由节点和链接组成的网络。 图论研究网络的性质（如可靠性），这是理论和实践的兴趣。研究人员致力于解决大网络内部存在小网络的问题。该研究在某些节点要求特殊可靠性条件的网络设计中具有潜在的应用价值。

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.