On structures of large graphs

Louisiana State University, Baton Rouge LA

Investigators

Abstract

In recent years, large-scale networks become more and more important in many fields of science. Examples of such networks include not only traditional networks like transportation networks and computer networks, but also social networks (like Facebook) and biological neural networks (like human brains). Since graphs are mathematical models of these networks, the study of these large-scale networks demands a better understanding of the behavior of large graphs. The topics under study in this research project are concerned with fundamental properties of large graphs. Results on these questions will have strong impact on many areas of graph theory. In particular, structure results coming out of this project could lead to more efficient algorithms for related problems on large graphs. These algorithms would in turn impact the study of large-scale networks from the real world. To be precise, the PI will study the following three fundamental problems: (1) He will characterize graphs that do not contain a large K_{3,n}-minor. (This graph is special because researchers in this area believe that it is the main reason for a high genus of a graph. The PI proposes to show that a 6-connected K_{3,n}-free graph must have a small genus or small tree-width.) (2) He will establish a splitter theorem for large 4-connectd graph. (These types of results are very fundamental and, as useful tools, they will have a very wide range of applications.) (3) He will characterize Petersen-free graphs that can be drawn on the projective plane. (There are reasons to believe that this class of graphs provide important building blocks for general Petersen-free graphs. A positive result here could shed new light on the general problem of characterizing Petersen-free graphs.)