Abstract:

Let $ G $ be an $ n $-order $ k $-cyclic graph. The $ k $-cyclic graph is a simply connected graph which the number of edges is equal to the number of vertices adding $ k-1 $. Let $ \mu_{1}(G) $ and $ \mu_{2}(G) $ be the largest eigenvalue and the second largest eigenvalue of the Laplacian matrix of $ G $, respectively. The Laplacian separator of graph $ G $ is defined as $ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $. In this paper, we study the maximun Laplacian separator of $ k $-cyclic graph with given order, and characterize the according extremal graph. The result generalizes the existing conclusions when $ k=1, 2, 3 $.

Key words: k-cyclic graph, Laplacian matrix, Laplacian separator