On the sparsity order of a graph and its deficiency in chordality
type: Item
instance of: scholarly article
title: On the sparsity order of a graph and its deficiency in chordality
zbMATH Open document ID: 0989.05073
author: Monique Laurent
published in: Combinatorica
publication date: 2002-06-25T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/11683
review text: For a graph \(G\) on \(n\) vertices \({\mathcal P}_G\) is the cone of \(n\times n\) positive semidefinite matrices with real or complex entries having a zero entry at every off-diagonal position corresponding to a non-edge in \(G\). The sparsity order of \(G\) is the maximum rank of a matrix lying on an extreme ray of the cone \({\mathcal P}_G\). The characterization of the graphs with sparsity order \(1\) was given earlier and the characterization of the graphs with sparsity order \(2\) was conjectured in the same paper. The main result of this paper is the proof of this conjecure.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 15B57
zbMATH DE Number: 1759070
zbMATH Keywords: graph
zbMATH Keywords: sparsity order
zbMATH Keywords: chordal graph
MaRDI profile type: Publication
OpenAlex ID: W2084407118
DOI: 10.1007/S004930100012
description: scientific article; zbMATH DE number 1759070