A graph for which the inertia bound is not tight

DOI10.1007/S10801-017-0768-0zbMATH Open1381.05046arXiv1609.02826OpenAlexW2963498117MaRDI QIDQ1704091FDOQ1704091

Authors: John Sinkovic 

Publication date: 8 March 2018

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

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.

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

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

zbMATH Keywords

independence numberweight matrix[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Cvetkovi%EF%BF%BD%EF%BF%BD+bound&go=Go Cvetkovi�� bound]inertia 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)

Cites Work

• Title not available (Why is that?)
• Weighted matrix eigenvalue bounds on the independence number of a graph
• Random graphs.

Cited In (2)

• Spectral upper bound on the quantum k-independence number of a graph
• The inertia bound is far from tight

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)