SPN graphs: when copositive = SPN

DOI10.1016/J.LAA.2016.07.018MaRDI QIDQ314749zbMATH OpenOpenAlexFDO

Authors Naomi Shaked-Monderer

Publication date 16 September 2016

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3176168 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• scientific article; zbMATH DE number 2205665 (Why is no real title available?)
• A test for copositive matrices
• Copositive optimization -- recent developments and applications
• Criteria for copositive matrices of order four
• Extreme copositive quadratic forms
• Graph theory
• Irreducible elements of the copositive cone
• Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
• On copositive matrices with -1, 9, 1 entries
• Remarks on the recursive structure of copositivity
• SPN completable graphs
• Some NP-complete problems in quadratic and nonlinear programming
• The Schur complement and its applications

Cited in

(8)

• SPN completable graphs
• On the generalized inverse of a copositive matrix
• 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
• The triangle graph \(T_6\) is not SPN
• Corrigendum to: ``SPN graphs: when copositive = SPN
• SPN graphs

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)