In this paper it is considered how graphs can be used to generate copositive matrices, and necessary and sufficient conditions are given for these generated matrices to then be irreducible with respect to the set of positive semidefinite plus nonnegative matrices. This is done through combining the well known copositive formulation of the stable set problem with recent results on necessary and sufficient conditions for a copositive matrix to be irreducible. By applying this result, tens of thousands of new irreducible copositive matrices of order less than or equal to thirteen were found. These matrices were then tested for being extreme copositive matrices, and it was found that in all but three cases this was indeed the case. It is also demonstrated in this paper that these matrices provide difficult instances to test approximations of the copositive cone against.
|Number of pages||15|
|Journal||Discrete applied mathematics|
|Early online date||5 May 2020|
|Publication status||Published - 15 Jun 2021|
- Stability number