Investigation Of Several Problems To The Everywhere H-Separable Graphs

The connexity of graphs is an important field to be investigated in graphtheory. By connexity studying, ones know more and more characters andproperties of graphs. The results ones obtained from the connexity studying areused to settle many practical problems, especially on the field of computer orcommunication networks. And some useful results are acquired. The connexityof graphs has received much attention. Its theoretical and practical meaning hasinterested many people who majored in graph theory. Through in-depth study,among the parameters: connectivity, edge-connectivity, local (edge-)connectivityof graphs, ones have attained a great lot of conclusions.Along with the study, ones find the parameters mentioned above onlyreflect how difficulty a system is destroyed. And these parameters are not usedto measure the breakage of the system, exactly. So, ones have made great effortsin search of new methods to study the connexity of graphs.In 1988, professor, Jia Xiaofeng put forward a new family of graph——everywhere h-separable graphs which is helpful to solving the maximumedges and maximum clique problems of graphs. Let h＞0 be an integer and Sis a (vertex)minimal cut of graph G. If |S| is not greater than h then we callS a lower h-cut of graph G. If for any vertex v∈V(G), there exists at leastone lower h-cut S and v∈S then the graph G is called an everywhereh-separable graph.By far, he has done much in-depth research about this new family of graphs,and educed a lot of results, especially on the maximum clique problems. In this paper, we partition the (vertex)minimal cuts into two categories:A-cut——a lower h-cut which does not intersect with any otherlower h-cuts of an everywhere h-separable graph; B-cut——the reverse ofthe former definition. Under the conditions of partitioning for minimal cuts andsome other new results, we discuss a new problem——additive-edge problemwhich is related to the connexity of graphs. And we introduce a new graphparameter——integrity which shows how difficulty to break down a graph at itsminimal cuts, and can reflect the breakage of destroying the graph, exactly.In this paper, additive-edge problem and integrity problem of everywhereh-separable graphs are primarily concerned.This paper is composed of five chapters, the primary contents are showedas follows.ChapterⅠgives a particular introduction about the history and currentsituation of the connexity of graphs, and points out the significance to study theeverywhere h-separable graphs and its integrity through analyzing thedeficiency of previously methods used to study the connexity of graphs.ChapterⅡis concerned with the minimal cuts of the everywhereh-separable graphs. Some results are given. Which is the foundation for theinvestigation of the everywhere h - separable graphs.ChapterⅢmainly discusses the additive-edge problem in an everywhereh-separable graph, under two conditions that A-cut is a cut-vertex andA- cut is neither a cut-vertex nor a clique. And, according to the properties ofeverywhere h- separable graphs and A-cuts, we characterize two sufficientlyconditions of constructing an everywhere h- separable graph.ChapterⅣinvestigates the integrity of an everywhere h- separable graph,and the relations between integrity and other graph parameters. Some bounds on the integrity are attained.ChapterⅤis the conclusion of the paper.