On The Spectral Radius Of The Square Of Graphs

The kth power of a connected graph G, denoted by Gk, is obtained from G by adding an edge between each pair of vertices within distance k. When k=2, G2 is exactly the square of G. The power graphs have many theoretic research as well as practical applications, e.g. the frequency assignment and the distance coloring problem arising from it. This thesis mainly deal with the spectral radii of the square of graphs. In 1973 Cvetkovic discussed the spectrum of the total graph of a regular graph, where the total graph of a graph is the square of the subdivision of the graph. In 2013 Das and Guo investigated the Laplacian eigenvalues of the square of graphs. Recently Miao and Fan discussed the distance coloring of graphs, and proved that p（Gk）≤p（G）k, i.e. the spectral radius of the kthe power of a graph is not greater than the kth power of the spectral radius of the graph. Except the above work, the work on the eigenvalues of the power graphs receives little attention.In this paper, we proved that if T is a tree of order n≥ 4, then where the first equality holds if and only if T= Pn, and the second equality holds if and only if T=Sn. This result is parallel with that of simple graphs. Let U be a acyclic graph of order n≥ 4. Then with equality if and only if U= C3（v） o Pn₂（v） or U= Cn, where v is a pendant vertex of Pn-2.When 5≤ n≤ 100, we verified that This implies that there exists difference between the spectral radii of a graph and its square.The organization of the thesis is as follows. In Chapter 1 we briefly introduce the development of spectral graph theory and the topic of this thesis, some concepts and notations, and the problem and main results in this thesis. In Chapter 2 we first discuss the perturbation result of the spectral radius of the square of a graph after one of its branches is relocated, and then using the result to characterize the maximum or minimum spectral radius of the square of trees. In Chapter 3 we give the upper or lower bounds of the spectral radii of the square of unicyclic graphs, and also investigate the maximum spectral radius of the square of unicyclic graphs with given girth or the trees with given diameter.