Study On The Signless Laplacian Spectral Radius And The Balanced Bipartitions Of Graphs

This paper consists of two parts. Firstly, we study the upper bound on the signless Laplacian spectral radius of simple graphs and planar graphs. For a graph, if there exists an orientation such that the maximum out-degree Δ+ is no more than half of the maximum degree Δ, by estimating the number of the semi-edge walks of the graph, we obtain a new upper bound of the signless Laplacian spectral radius of the graph, that is Moreover, combining with the result of the edge decomposition of a planar graph by D.Goncalves, a new upper bound of the signless Laplacian spectral radius of a planar graph is presented, that is,Secondly, we study the upper bound on the minimum balanced bipartition of simple graphs and planar graphs. Given a graph, we use the adjacency matrix of the graph to express the number of edge cuts of a balanced bipartition, and obtain a new upper bound on the minimum balanced bipartition, that is, m and n are the number of edges and vertices of the graph, respectively. Moreover, for a planar graph, if the number of edges is less than twice of the number of vertices, then there must exist a balanced bipartition such that the number of edge cuts is no more than the number of vertices.