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
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
graph spectra
0 references
signless Laplacian matrix
0 references
spectral radius
0 references
Hamiltonian graph
0 references
perfect matching
0 references
0 references