Some Results About Polynomials Of Signed Graph

Let G=(V(G),E(G))be a simple graph of order n and size m,and letσ:E(G)→{+1,-1}be a mapping defined on the edges of G.Then,the pairΓ=(G,σ)is called a signed graph of G,where G is its underlying graph whileσis its sign function.This paper mainly study polynomials related to signed graphs by using combinatorial and algebraical methods.Firstly,we define a new polynomial――the average Laplacian polynomial of a graph G,that is,the average of Laplacian polynomials of all signed graphs with underlying graph G.We give a combinatorial expression for the coefficients of this new polynomial.And the relations between the average Laplacian polynomial and other polynomials,especially,the matching polynomial are also studied.Secondly,given a signed graphΓ=(G,σ),we define three classes of signed transform graphs:signed middle graph,signed triangular extension graph and signed total graph.When the graph G is regular,we express the adjacency,Laplacian and signless Laplacian polynomials of these signed transform graphs in terms of that of original signed graph.These results generalize the corresponding results of unsigned graphs.Finally,we define a mappingΘfrom the set of sign functions on the k-subdivision S_k(G)to that of G.Using the mappingΘ,we show that characteristic polynomials related to signed graphΓ=(S_k(G),η)can be expressed by the corresponding polynomial ofΓ=(G,Θ_η)if graph G is regular.Applying the results,we extend the relations between the average Laplacian polynomial and the matching polynomial established before further.