Some Results On Dissection Of Graphs

The dissection of graphs, introduced by Randic in 1979, is a useful moleculedescriptor of chemical molecular graphs. The dissection of graph G, denoted byD(G), is a 2-dimensional integer vector (x,y), defined recursively as follows:(1) If G = K1, then D(G) = (1,0).(2) If G = K2, then D(G) = (0,1).(3) If G is not connected, then D(G) =∑_i=1^rD(Gi), where G1,G2,···,Grare all the components of G; if G is a connected graph with order at least three,then D(G) =∑_v∈V(G) D(G - v).We denote the first coordinate of the dissection D(G) = (x,y) of a graphG as a(G), and the second one as b(G). And D(G1) = D(G2) if and only ifa(G1) = a(G2) and b(G1) = b(G2). There are several graph invariants of a veryhigh-resolution power that may be of interest for graph isomorphism testing. In2000, Randic et al. posed the following conjecture: for two trees T1 and T2,D(T1) = D(T2) if and only if T1～= T2. It is very interesting but di?cult to bestudied, so far it is still an open problem.Xu et al. investigated some properties of the dissection of graphs recently.In particular, they gave sharp bounds for a(T) and b(T) for trees of fixed order.i.e., among all trees of order n, the star graph K1,n has the maximum a(T) andb(T), the path Pn has the minimum a(T) and b(T).In chapter one, we introduce the background, terminologies and some resultswhich have obtained by Xu et al. Chapter two is devoted to studying bounds fordissection of unicyclic graphs. Let ?n?3 denote the unicyclic graph with order nobtained from K3 and Pn?3 by joining a vertex of K3 to one endvertex of Pn?3,K1+,n?1 denote the unicyclic graph with order n obtained from K1,n?1 by joiningits two pendant vertices. We give the dissection of ?n and K1+,n, and prove thatamong all unicyclic graphs of order n≥6, the graph ?n?3 has the minimum a(G) and b(G), and the graph K1+,n?1 has maximum a(G) and b(G).In chapter three, we introduce a new method in computing the dissectionof graphs, by which we determine dissection of complete r-partite graphs andKn∨Km, where Kn∨Km is obtained from two vertex disjoint graphs Kn andKm by joining every vertex of Kn to every vertex in Km.In chapter four, we prove that among all bicyclic graphs of order n≥7, thegraph ?n??6 has the minimum a(G) and b(G), where ?n??6 is the bicyclic graphobtained from two K3 and Pn?6 by joining two end vertices of Pn?6 to one vertexof each K3.