A sharp lower bound on the signless Laplacian index of graphs with \((\kappa,\tau)\)-regular sets (Q1642897)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A sharp lower bound on the signless Laplacian index of graphs with \((\kappa,\tau)\)-regular sets
scientific article

    Statements

    A sharp lower bound on the signless Laplacian index of graphs with \((\kappa,\tau)\)-regular sets (English)
    0 references
    0 references
    0 references
    15 June 2018
    0 references
    Let \(G=(V,E)\) be a graph. A \((\kappa,\tau)\)-regular set \(S\) is a subset of \(V\), inducing a \(\kappa\)-regular subgraph such that every vertex not in \(S\) has \(\tau\) neighbours in \(S\). The authors bring several different conditions under which the existence of a \((\kappa,\tau)\)-regular set \(S\) in \(G\) implies that the spectral radius of the signless Laplacian matrix of \(G\) is larger than \(\kappa+\tau\). This bound has a potential application for checking the nonexistence of Hamiltonian cycles or perfect matchings in graphs since the edge sets of Hamiltonian cycles and perfect matchings in the line graph correspond to \((2,4)\)-regular sets and \((0,2)\)-regular sets, respectively. The authors test graphs from Mathematica's GraphData library and show that a number of them does not fulfill these bounds implying that they do not have a Hamiltonian cycle or a perfect matching.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    graph spectra
    0 references
    signless Laplacian matrix
    0 references
    spectral radius
    0 references
    Hamiltonian graph
    0 references
    perfect matching
    0 references
    0 references