Graphs With Fixed Diameter Minimizing The Spectral Radius

The spectral radius p(G) of a graph G is the largest eigenvalue of its adjacency ma-trix. Spectral radius plays an important role in modeling virus propagation in networks. In fact, the smaller the spectral radius, the larger the robustness of a network against the spread of viruses. About graphs with small spectral radius, all graphs with spectral radius at most were determined in the literature. Woo and Neumaier discovered that a connected graph G with2<p(G)<3/2(?) is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Not all quipus have spectral radius between these two numbers. Quipus are graphs we focus on in this dissertation.A minimizer graph, denoted by Gn,D,min is a graph which has the minimal spec-tral radius among all connected graphs on n vertices with diameter D. So far, for D∈{1,2,「n/2」, n-5, n-4, n-3, n-2, n-1} and n large enough, the minimizer graph Gn,D,min has been determined; and it was proved that GGn,D,min must be a tree for D≥(2n-2)/3. In this dissertation, we consider the cases n/2≤D≤(2n-3)/3and D=n-e, where e is a positive integer, and obtain the following results.●Quipus with spectral radii between2and3/2(?) are characterized and given respec-tively a lower bound and an upper bound of their diameters. Both bounds are tight.●Assume n≥13. For n/2≤D≤(2n-4)/3, the minimizer graph Gn,D,min are determined, which are all closed quipus. For D=(2n-3)/3, the minimizer graph is proved to be a tree. This result fill the research gap of Gn,D,min for D from n/2to (2n-3)/3.●For e≥6and sufficiently large n, the minimizer graph Gn,D,min is characterized and proved to have internal path of almost equally long (different by at most1or2). These results are best possible as shown by cases e=6,7,8, where Gn,D,min are completely determined.●For n=s(e-4)+6, where s is an integer, the minimizer graph Gn,D,min is determined. Besides, we discover that a family of quipus share the same spectral radius.