The clique number and the smallest Q-eigenvalue of graphs

DOI10.1016/J.DISC.2016.02.002zbMATH Open1333.05192arXiv1508.01784OpenAlexW2216070917MaRDI QIDQ267202FDOQ267202

Authors: Vladimir Nikiforov, Carla Oliveira, Leonardo Silva de Lima 

Publication date: 8 April 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Eigenvalues of the Laplacian of a graph^∗
• On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs
• The local density of triangle-free graphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• Properties of spectra of graphs and line graphs
• A simple group of order 44,352,000
• Title not available (Why is that?)
• Linear combinations of graph eigenvalues
• Extrema of graph eigenvalues
• The smallest eigenvalue of the signless Laplacian
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to make a graph bipartite
• Making a \(K_4\)-free graph bipartite
• On conjectures involving second largest signless Laplacian eigenvalue of graphs

Cited In (14)

• The Spectrum of Triangle-Free Graphs
• Merging the \(A\)- and \(Q\)-spectral theories
• The signless Laplacian spectral radius of graphs with a prescribed number of edges
• Quantum walks on blow-up graphs
• Bounds for the largest and the smallest \(A_\alpha\) eigenvalues of a graph in terms of vertex degrees
• On a conjecture related to the smallest signless Laplacian eigenvalue of graphs
• Title not available (Why is that?)
• 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)