Integer flows, circular flow indices and modulo orientations

点击翻译按钮获取中文摘要

This award supports the principal investigator's research in graph theory, and specifically flows, coloring, and connectivity in graphs. This area is closely related to computer science, operations research, data mining, and the neurosciences, where graphs are abstract mathematical notions used to model networks, such as communication and transportation networks, social networks, surveillance data, pathways in bioinformatics, and neural-networks. Various graph coloring problems have been considered as effective models for radio channel assignment/distribution, and flow problems originally arise in optimizing traffic or network. This project is concerned with structural problems in networks. Integer flow theory, introduced by Tutte as a dual of the graph/map coloring problem, is the major subject of this proposed project. Recently, the principal investigator (collaborating with Lovasz, Thomassen and Wu) successfully proved that every 6-edge-connected graph admits a nowhere-zero 3-flow, and (collaborating with Thomassen and the team at WVU) discovered a relation between strongly connected orientations and circular flow indices. The principal investigator will continue his research work in this direction by determining the flow indices for graphs with various connectivity, investigating flows of graphs embedded on non-orientable surfaces, studying modulo orientations of less connected graphs for better solutions to Tutte's flow conjectures.