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

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.