Bounding the gap between extremal Laplacian eigenvalues of graphs (Q2497240)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Bounding the gap between extremal Laplacian eigenvalues of graphs
scientific article

    Statements

    Bounding the gap between extremal Laplacian eigenvalues of graphs (English)
    0 references
    0 references
    4 August 2006
    0 references
    Let \(G\) be a graph whose Laplacian eigenvalues are \(0=\lambda_{1}\leq \lambda_{2}\leq \dots\leq \lambda_{n}\). Motivated by the property of extremal Laplacian eigenvalues to provide a possible value range for the density of cuts in a graph, the author is interested in providing lower bounds on the gaps \(\frac{\lambda_{n}}{\lambda_{2}}\) and \(\lambda_{n} - \lambda_{2}\) between the extremal non-trivial Laplacian eigenvalues in a connected graph. The author first observes a simple ratio bound \[ \frac{\lambda_{n}}{\lambda_{2}}\geq\frac{\Delta(G)+1}{\delta(G)}, \] characterizes the case of equality and then conjectures that this bound can be further improved by \(O(\frac1{n^{2}})\) a.e. for random graphs. Further, the author uses two reverse Cauchy-Schwarz inequalities, that is the Pólya-Szegö inequality and the Ozeki inequality, to get additional lower bounds on \(\frac{\lambda_{n}}{\lambda_{2}}\) in Theorem 3.5 and on \(\lambda_{n} - \lambda_{2}\) in Theorem 3.6. At present, these theorems hold only for connected regular graphs, although they can be extended to hold for other graphs by letting the vector \(a\) in the proofs of these theorems be a vector of vertex degrees (either the \(n-1\) smallest or the \(n-1\) largest degrees).
    0 references
    Laplacian matrix
    0 references
    cut
    0 references
    reverse Cauchy-Schwarz inequality
    0 references
    Pólya-Szegö inequality
    0 references
    Ozeki inequality
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references