| It is well known that the spectrum of weight graphs are often used to solve problems.Thisis because graphes of the design of networks or electronic circuits are usually weighted.G is a simple graph, vertex set is V = {v1,v2...vn},edge set is E = {e1,e2...em}. letW = {w1,w2...wm}be the weighted set,wi is decrease and wi > 0,i = 1,2...m.Define afunction f:E→W,f is called weighted function. Gf = (V,E,W,f) is called weightedgraph.The Laplacian matrix of Gf(W) is Lf. The eigenvalues of Lf is called the Laplacianeigenvalue of Gf(W). In 1973 year,Fielder advanced that graph G is connected if andonly if the second smallest Laplacian eigenvalue un-1 > 0 of G . So un-1 is called alge-braic connectivity of G by Fielder ,denote a(G). Similar,the second smallest Laplacianeigenvalue of Gf(W) is called the algebraic connectivity of weighted graph Gf(W) . Onthe base of this,in this paper,we study the changing situation of algebraic connectivity ofthe weighted graph Hf by grafting translation.In this paper,we study three contents:how toweight k regular graph.To every vertex of k regular graph increase a set Niwhich containsl points,1≤l≤n,i = 1,2...n, to every vertices of vi and vertices of Ni connected a edge,give a weight of every increase edge.Let the new weighted graph is Hf.We give the relationof characterists polynomial of Hf and Gf.How to change the algebraic connectivity of Hfafter grafting translation.We can get as small as algebraic connectivity of weighted graph.Thepaper is devided into four section.In section one we introduce the history of the algebraic connectivity of weighted graphand the main results.In section two,we introduce the terminologies.In section three,first we give the relation of weighted function f and perron vector,themain results as follows:theorem3.1:Let Gf be a k regular graph with n (n > 3) vertices and m edges,then theweighted function f is defined f(e) = w1 = ... = wm,(e∈Gf,wi > 0,i = 1, 2...m).theorem3.3: The adjacency matrix and Laplacian matrix of Gf are Af and Lf,respectively.For every vertices of Gf,the weighted degree is a constant C,(C > 0).If Af has eigenvalue θ1,θ2...θn,then the Lf has eigenvalue C -θ1,C -θ2...C -θn .theorem3.4: Let Gf be a k regular graph, Hf is construct by the following way:(1)to anyvertices of Gf increase a set Niwhich contains l points,1≤l≤n,i = 1, 2...n(2)to everyvertices of vi and vertices of Ni connected a edge.If f(e) = w1,e∈Gf, thenf(viNi) = w2and w1 > w2 > 0.theorem3.5:Hf and Gf are the weighted graph in Theorem 3.4. Let PAf(λ) is the charac-terists polynomial of adjacency matrix of weighted Gf.Let PLf(λ) is the characterists poly-nomial of Laplacian matrix of weighted Gf.PAf(λ) is the characterists polynomial of adja-cency matrix of weighted Hf.PLf(λ) is the characterists polynomial of Laplacian matrix ofweighted Hf.Then we have: .In section four :We used the grafting translation,discussed the changing situation of alge-braic connectivity of weighted graph Hf,get as smaller as algebraic connectivity of weightedgraph,the main results as follows:theorem4.2:Let v1,v2 be two different dependent vertices,let v1∈N(v0),v2∈N(v0),wv0v1= wv0v2 = w2≠a(Hf),if H'f = Hf\{v0v1} + {v1v2},and the weight of new edge wv1v2 =wv0v2 = w2≠a(Hf),then a(H'f) < a(Hf).theorem4.4:In selecting u0 place connection length is the pk path,pk = u0u1...uk,k≥1,theweight of every edge is w,w > af > 0.Let X be the unit characterists vector correspondto the algebraic connectivity af of weighted graph Hf .If the component of vector X bexu0 > 0,then {xpk} is a positive monotonous rise sequence.theorem4.5:Let X be the unit characterists vector correspond to the algebraic connectiv-ity af of weighted graph Hf, xvi correspond to vi,In selecting u0 place connection lengthesare k paths and l paths,denote Pk+1 = u0u1...uk,Pl+1 = u0v1...vk,k≥l≥1,on the twopathes,the weight is equal w2,H'f = Hf\{vl-1vl} + {ukvl}, then a(H'f)≤a(Hf),whenxv0 = 0,the equal sign is tenable.theorem4.9:If u1 and v1 be two different dependant vertices of Tf,v1∈N(v),u1∈N(u),wuu1 = w1,wvv1 = w2,w1 > w2, if Tf = Tf\{vv1} + {u1v1},xu > xu1 > xv > 0,thena(T'f) < a(Tf).
|
PDF Full Text Request