New analytical lower bounds on the clique number of a graph

DOI10.1080/10556788.2016.1172578zbMATH Open1384.05126OpenAlexW2346130554MaRDI QIDQ5268926FDOQ5268926

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

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

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

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)

Cites Work

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

Cited In (4)

• Continuous cubic formulations for cluster detection problems in networks
• A simpler characterization of a spectral lower bound on the clique number
• A new proof of the Fisher-Ryan bounds for the number of cliques of a graph
• Exact bounds on the order of the maximum clique of a graph.

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)