A graph for which the inertia bound is not tight

DOI10.1007/S10801-017-0768-0MaRDI QIDQ1704091zbMATH OpenOpenAlexFDO

Authors John Sinkovic

Publication date 8 March 2018

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

independence numberweight matrixinertia boundCvetković bound

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Abstract: The inertia bound gives an upper bound on the independence number of a graph by considering the inertia of matrices corresponding to the graph. The bound is known to be tight for graphs on 10 or fewer vertices as well as for all perfect graphs. The question has been asked as to whether the bound is always tight. We show that the bound is not tight for the Paley graph on 17 vertices as well as for the graph obtained from Paley 17 by deleting a vertex.

Recommendations

• An inertial lower bound for the chromatic number of a graph
• A relative bound for independence
• Inertia sets for graphs on six or fewer vertices
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• Bounds for the positive and negative inertia index of a graph

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• Random graphs.
• Weighted matrix eigenvalue bounds on the independence number of a graph

Cited in

(4)

• The inertia bound is far from tight
• Inertia, independence and expanders
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• An inertial lower bound for the chromatic number of a graph

This page was built for publication: A graph for which the inertia bound is not tight

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