The clique number and the smallest Q-eigenvalue of graphs

DOI10.1016/J.DISC.2016.02.002MaRDI QIDQ267202zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov, Carla Oliveira, Leonardo Silva de Lima

Publication date 8 April 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.01784

zbMATH Keywords

Laplacianblow-up graphsclique numbercomplete subgraphsextremal problemsignless Laplacian

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $q_{min}(G)$ stand for the smallest eigenvalue of the signless Laplacian of a graph $G$ of order $n.$ This paper gives some results on the following extremal problem: How large can $q_{m}inleft(Gight)$ be if $G$ is a graph of order $n,$ with no complete subgraph of order $r+1?$ It is shown that this problem is related to the well-known topic of making graphs bipartite. Using known classical results, several bounds on $q_{min}$ are obtained, thus extending previous work of Brandt for regular graphs. In addition, using graph blowups, a general asymptotic result about the maximum $q_{min}$ is established. As a supporting tool, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated.

Recommendations

• On the smallest signless Laplacian eigenvalue of graphs
• The smallest signless Laplacian spectral radius of graphs with a given clique number
• Maxima of the \(Q\)-index: graphs with bounded clique number
• The minimum spectral radius of signless Laplacian of graphs with a given clique number
• scientific article; zbMATH DE number 6612432

Cites work

• scientific article; zbMATH DE number 426334 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3349865 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A simple group of order 44,352,000
• Eigenvalues of the Laplacian of a graph^∗
• Extrema of graph eigenvalues
• How to make a graph bipartite
• Linear combinations of graph eigenvalues
• Making a K₄-free graph bipartite
• On conjectures involving second largest signless Laplacian eigenvalue of graphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs
• Properties of spectra of graphs and line graphs
• The local density of triangle-free graphs
• The smallest eigenvalue of the signless Laplacian

Cited in

(14)

• The Spectrum of Triangle-Free Graphs
• The signless Laplacian spectral radius of graphs with a prescribed number of edges
• Merging the \(A\)- and \(Q\)-spectral theories
• Bounds for the largest and the smallest \(A_\alpha\) eigenvalues of a graph in terms of vertex degrees
• Quantum walks on blow-up graphs
• On a conjecture related to the smallest signless Laplacian eigenvalue of graphs
• scientific article; zbMATH DE number 2096437 (Why is no real title available?)
• On the least signless Laplacian eigenvalue of a non-bipartite connected graph with fixed maximum degree
• Note on the sum of the smallest and largest eigenvalues of a triangle-free graph
• On the least eigenvalue of \(A_\alpha \)-matrix of graphs
• On the smallest signless Laplacian eigenvalue of graphs
• Maximizing the least Q-eigenvalue of a unicyclic graph with perfect matchings
• On the smallest eigenvalue of D_α-matrix of connected graphs
• The clique numbers of regular graphs of matrix algebras are finite

This page was built for publication: The clique number and the smallest \(Q\)-eigenvalue of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q267202)