New analytical lower bounds on the clique number of a graph

DOI10.1080/10556788.2016.1172578MaRDI QIDQ5268926zbMATH OpenOpenAlexFDO

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

assortativity coefficientclique numberErdös-Rényi modelMotzkin-Straus formulationpower-law graphsspectral graph theory

Mathematics Subject Classification ID

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

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 bounds for the clique and independence numbers of graphs
• Spectral Radius and Degree Sequence
• The average distance and the independence number
• The Average Distance in a Random Graph with Given Expected Degrees
• The independence number of graphs in terms of degrees
• The Structure and Function of Complex Networks
• The University of Florida sparse matrix collection
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications

Cited in

(7)

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

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)