SPN graphs: when copositive = SPN

DOI10.1016/J.LAA.2016.07.018zbMATH Open1345.05111arXiv1604.02172OpenAlexW2335862003MaRDI QIDQ314749FDOQ314749

Naomi Shaked-Monderer

Publication date: 16 September 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: A real symmetric matrix $A$ is copositive if $x^{T}Axge0$ for every nonnegative vector $x$. A matrix is SPN if it is a sum of a real positive semidefinite matrix and a nonnegative one. Every SPN matrix is copositive, but the converse does not hold for matrices of order greater than $4$. A graph $G$ is an SPN graph if every copositive matrix whose graph is $G$ is SPN. In this paper we present sufficient conditions for a graph to be SPN (in terms of its possible blocks) and necessary conditions for a graph to be SPN (in terms of forbidden subgraphs). We also discuss the remaining gap between these two sets of conditions, and make a conjecture regarding the complete characterization of SPN graphs.

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

Recommendations

• Corrigendum to: ``SPN graphs: when copositive = SPN
• SPN completable graphs
• SPN graphs
• Graph Isomorphism is in SPP
• The poset on connected graphs is Sperner
• scientific article; zbMATH DE number 3861193
• Homomorphisms of sparse signed graphs
• Some coinductive graphs
• On completely positive graphs and their complements
• scientific article; zbMATH DE number 510852

zbMATH Keywords

copositive matricesSPN matrices

Mathematics Subject Classification ID

Positive matrices and their generalizations; cones of matrices (15B48) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (05C99) Sign pattern matrices (15B35)

Cites Work

• Title not available (Why is that?)
• The Schur complement and its applications
• Some NP-complete problems in quadratic and nonlinear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• On copositive matrices with -1, 9, 1 entries
• Irreducible elements of the copositive cone
• SPN completable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A test for copositive matrices
• Copositive optimization -- recent developments and applications
• Criteria for copositive matrices of order four
• Extreme copositive quadratic forms
• Remarks on the recursive structure of copositivity
• Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
• Title not available (Why is that?)

Cited In (6)

• On the generalized inverse of a copositive matrix
• Title not available (Why is that?)
• Hypergraph characterizations of copositive tensors
• On standard quadratic programs with exact and inexact doubly nonnegative relaxations
• Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
• Corrigendum to: ``SPN graphs: when copositive = SPN

This page was built for publication: SPN graphs: when copositive = SPN

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