The Nullity Of Compound PED-graphs

The spectrum of a graph G is the set of eigenvalues of the adjacency matrix of G. The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum, denoted byη(G). PED-graphs are a class of new defined graphs by Qiongxiang Huang in 2006, the nullity of PED-graphs has been studied in depth. In this thesis, we mainly study the relationship between the maximum matching number and the nullity of some compound form PED-graphs and some order compound form PED-graphs and each subgraph.In section one,we introduced the study background about this paper and domestic and foreign research situations.In section two, we introduce the terminology and main results. Let G be an arbitrarily simple graph of order n, A(G) is the adjacency matrix of graph G. Let r be the rank of A(G), by the definition of nullity,η(G)=n-r. In the reference [2], define a class of new graphs, PED-graphs: A graph G of order n is called a PED-graphs if it has an edges sequence: e₁= x₁y₁, e₂=x₂y₂,…,e_i=x_iy_i,…,e_r=x_ry_r such that the following three conditions are satisfied: (1) G_i=_i-1\{x_i,y_i}, where i=1,2,…,r and G₀=G (2) e_i=x_iy_i is a pendent edge of G_i-1 (3) G_r is the graph of (n-2r)'s isolated vertices. Clearly, tree and forest are PED-graphs, and there exists PED-graphs that is not tree and forest. The reference [2] gives the nullity of PED-graphs, i.e.η=n-2m, where m is the maximum matching number.In section three, we study the relationship between the maximum matching number and the nullity of some compound form PED-graphs and each subgraph. Let G be a graph of order n, m is the maximum matching number,ηis the nullity of G. If G and path P_k compound, i.e. make each vertex of P_k to replace by G, obtained a graph,denoted by P_k-G we called the vertex of G that incident to the edge of P_k is the composition vertices,then when all the composition vertices are reserved vertices, m(P_k-G)=km+k-1,η(P_k-G)=k_η-2k+2,η≥2; when all the composition vertices are deleted vertices,m(P_k-G)=km,η(P_k-G)=kη. If contracted all the edges that belong to P_k of P_k-G,obtained a graph, denoted by P_k·G then when all the composition vertices are reserved vertices, m(P_k·G)=km,η(P_k-G)=kη-k+1,η≥2; when all the composition vertices are deleted vertices,m(P_k·G)=km-k+1,η(P_k·G)=kη+k-1. If G and cycle C_k compound, obtained a graph, denoted by C_k-G then when all the composition vertices are reserved vertices,m(C_k-G)=km+k,η(C_k-G)=kη-2k,η≥2; when all the composition vertices are deleted vertices, m(C_k-G)=km,η(C_k-G)=kη. If contracted all the edges that belong to C_k of C_k-G, obtained a graph, denoted by C_k·G then when all the composition vertices are reserved vertices, m(C_k·G)=km,η(C_k·G)=kη-k,η≥2; when all the composition verticesare deleted vertices, m(C_k·G)=km-k,η(C_k·G)=kη+k. If G and star S_k+1 (except the center vertex) compound, obtained a graph, denoted by S_k·G+1, then when all the compositionvertices are reserved vertices, m(S_k·G+1)=km+1,η(S_k·G+1)=kη-1,η≥1; when all the composition vertices are deleted vertices, m(S_k·G+1)=km,η(S_k·G+1)=kη+1. If G and complete binary tree compound,obtained a graph, simple denoted by G', then when all the composition vertices are reserved vertices, m(G')=(2^k-1)m+2^k-1-1,η(G')= (2^k-1)η-2^k+2,η≥2; when all the composition vertices are deleted vertices, m(G') = (2^k-1)m,η(G')=(2^k-1)η. If forks completely G with l floors k-branches the tree compound, obtained a graph, denoted by G", then when all the composition vertices are reservedvertices, m(G")=(?),η(G")=(?),η≥2; when all the composition vertices are deleted vertices, m(G")=(?),η(G")=(?).In section four, we main promotes above results to the general form, i.e. for k arbitrarilysimple graph G₁,G₂,…,G_k,|V(G_i)|=n_i,i=1,2,…,k, the maximum matching number are m₁,m₂,…,m_k, respectively, the nullities areη₁,η₂,…,η_k, respectively. If G₁,G₂,…,G_k compound with path P_k, cycle C_k,star S_k+1(except the center vertex), respectively.i.e. make all the vertices of P_k, C_k, S_k+1 to replaced by G₁,G₂,…,G_k, respectively,the results graphs are the order compound graphs. Besides we make (2^k-1)'s different PED-graphs compound with complete binary tree. Study the relationship between the maximum matching number and the nullity of these order compound form PED-graphs and each subgraph. The main arithmetic are similar to the study of compound PED-graphs in above.