New analytical lower bounds on the clique number of a graph

DOI10.1080/10556788.2016.1172578MaRDI QIDQ5268926zbMATHOpenAlexFDO

Authors Vladimir Stozhkov, Grigory Pastukhov, Eduardo L. Pasiliao, Vladimir Boginski

Publication date 21 June 2017

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10556788.2016.1172578

zbMATH Keywords

spectral graph theoryclique numberpower-law graphsMotzkin-Straus formulationassortativity coefficientErdös-Rényi model

Mathematics Subject Classification ID

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

Recommendations

• Exact bounds on the order of the maximum clique of a graph.
• Lower bounds for the clique and the chromatic numbers of a graph
• A simpler characterization of a spectral lower bound on the clique number
• A generalization for the clique and independence numbers
• A new lower bound on the independence number of graphs

Cites work

• A fast algorithm for the maximum clique problem
• A lower bound on the independence number of a graph
• A note on the independence number of triangle-free graphs. II
• Connected components in random graphs with given expected degree sequences
• Eigenvalues and forbidden subgraphs. I.
• Emergence of Scaling in Random Networks
• Exact bounds on the order of the maximum clique of a graph.
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Independence and the Havel-Hakimi residue
• Independence in connected graphs
• Independence, odd girth, and average degree
• Interpolating between bounds on the independence number
• Large cliques in a power-law random graph
• Lower bounds for the clique and the chromatic numbers of a graph
• Lower bounds on the stability number of graphs computed in terms of degrees
• Maxima for Graphs and a New Proof of a Theorem of Turán
• More spectral bounds on the clique and independence numbers
• Networks. An introduction.
• On clique relaxation models in network analysis
• On the independence number of a graph in terms of order and size
• Power-law distributions in empirical data
• Some Inequalities for the Largest Eigenvalue of a Graph
• Spectral Radius and Degree Sequence
• Spectral bounds for the clique and independence numbers of graphs
• The Average Distance in a Random Graph with Given Expected Degrees
• The Structure and Function of Complex Networks
• The University of Florida sparse matrix collection
• The average distance and the independence number
• The independence number of graphs in terms of degrees
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications

Cited in

(6)

• A new proof of the Fisher-Ryan bounds for the number of cliques of a graph
• A simpler characterization of a spectral lower bound on the clique number
• Improving upper bounds for the clique number by non-valid inequalities
• Continuous cubic formulations for cluster detection problems in networks
• Exact bounds on the order of the maximum clique of a graph.
• Lower bounds on paraclique density

Describes a project that uses

Uses Software

• SparseMatrix

This page was built for publication: New analytical lower bounds on the clique number of a graph

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