Advanced Search

In this paper we consider the following problem: Over the class of all simple connected unicyclic graphs on $n$ vertices with girth $g$ ($n$, $g$ being fixed), which graph minimizes the Laplacian spectral radius? Let $U_{n,g}$ be the lollipop graph obtained by appending a pendent vertex of a path on $n-g$ $(n>g)$ vertices to a vertex of a cycle on $g\ge 3$ vertices. We prove that the graph $U_{n,g}$ uniquely minimizes the Laplacian spectral radius for $n\ge 2g-1$ when $g$ is even and for $n\ge 3g-1$ when $g$ is odd.

The Wiener index of a connected graph is defined as the sum of the distances between all unordered pairs of its vertices. We characterize the graphs which extremize the Wiener index among all graphs on $n$ vertices with $k$ pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on $n$ vertices with $s$ cut-vertices.