Internal Partitions Of Finite Graphs

The internal partition problem,within a branch of the mathematical field of graph theory,is an interesting problem to be solved.The internal partition problem is a split-ting of the vertex set of an n-vertex graph G =(V,E),i.e.,V into two non-empty parts,such that each vertex has at least half of its neighbors in its own part.The internal partition problem compared to the figure,the conventional graph theory to solve more research is on the external parition problem and a variety of cutting edge issues.But for the existence of the internal partition of a finite graph,as well as which classes of graphs have internal parition and bisection,a related intriguing concept in this area,in more cases is still pending.It is often a difficult task to find an internal partition of a fixed classes of graphs or to construct a extremal graph that does not exist internal parti-tion.And because of its wide range of applications within the internal partition,not only in the field of mathematical theory research,research in many areas of economics and sociology have also been associated with the internal partition problem,and therefore within the research of the internal partition problem is very significant.It has been conjectured that,for n>N(d),every d-regular graph of order n has a([d/2].[d/2])-partition.In this paper,we analyze the internal partition problem of finite graphs from three aspects:related work,main theorem and other research.This article first review the origin and background of the internal partition problem,highlighting the pioneering work done on the issue of internal partitions by Thomassen and Stiebitz account.Then a weak-internal partition within major research paper,an(s,t)-partition of a graph G =(V,E)is a partition of V = V1 U V2 such that ?(G[V1])?s and b(G[V2])?t.In this paper we prove that every d-regular graph of order n has a([d/2],[d/2?)-partition(called a weak internal partition)for d<9,the exact bound of N(d)in n ? N(d)and some extremal graphs that do not exist internal partition.After the main theorem in this paper,we introduce some studies on the external partition and the bisection,which are closely related to the internal partition problem,and include some derivation study of Ban and Linial on the partitions of complementary graphs and cubic graphs.Finally,this paper made a discussion of some of the challenges in the internal partition problem,and try to explore some research and ideas.