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. It is natural to question whether the bound is always tight. We show that the bound is not tight for the Paley graph on 17 vertices as well as its induced subgraph on 16 vertices.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Interesting Graphs and their Colourings, unpublished lecture notes C. Godsil (2004).
See footnote 1.
Independence number of Paley graphs-IBM Research. Data published online at http://www.research.ibm.com/people/s/shearer/indpal.html.
References
Bollobás, B.: Random Graphs. Cambridge University Press, Cambridge (2001)
Elzinga, R.J.: The Minimum Witt Index of a Graph. PhD thesis, Queen’s University. http://hdl.handle.net/1974/682 (2007)
Elzinga, R.J., Gregory, D.A.: Weighted matrix eigenvalue bounds on the independence number of a graph. Electron. J. Linear Algebra 20, 468–489 (2010)
Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001)
Rooney, B.: Spectral Aspects of Cocliques in Graphs. PhD thesis, University of Waterloo. http://hdl.handle.net/10012/8409 (2014)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sinkovic, J. A graph for which the inertia bound is not tight. J Algebr Comb 47, 39–50 (2018). https://doi.org/10.1007/s10801-017-0768-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-017-0768-0