Operations Research Transactions

   

The second maximum (Laplacian)separator

  

  • Received:2018-03-21 Revised:2018-06-12 Published:2019-03-05

Abstract: Let $G$ be a unicyclic graph of order $n$, $\lambda_{1}(G)$ and $\lambda_{2}(G)$ be the largest eigenvalue and second largest eigenvalue of the adjacent matrix of $G$, $\mu_{1}(G)$ and $\mu_{2}(G)$ be the largest eigenvalue and second largest eigenvalue of the Laplacian matrix of $G$, respectively. The separator of $G$ is defined as $S_{A}(G)=\lambda_{1}(G)-\lambda_{2}(G)$. The Laplacian separator of $G$ is defined as $S_{L}(G)=\mu_{1}(G)-\mu_{2}(G)$. In this paper, we respectively study the second maximum separator and second maximum Laplacian separator of unicyclic graphs with given order, and characterize the according extremal graphs.

Key words: Unicyclic graph, separator, Laplacian separator