Graphs with sparsity order at most two: the complex case

DOI10.1080/03081087.2016.1274362MaRDI QIDQ4603775zbMATH OpenOpenAlexFDO

Authors E. M. Klem, Sanne ter Horst

Publication date 19 February 2018

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

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

zbMATH Keywords

forbidden subgraphssparsity ordermatrix cones

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hermitian, skew-Hermitian, and related matrices (15B57) Structural characterization of families of graphs (05C75) Convex sets and cones of operators (47L07)

Abstract: The sparsity order of a (simple undirected) graph is the highest possible rank (over $mathbbR$ or $mathbbC$) of the extremal elements in the matrix cone that consists of positive semidefinite matrices with prescribed zeros on the positions that correspond to non-edges of the graph (excluding the diagonal entries). The graphs of sparsity order 1 (for both $mathbbR$ and $mathbbC$) correspond to chordal graphs, those graphs that do not contain a cycle of length greater than three, as an induced subgraph, or equivalently, is a clique-sum of cliques. There exist analogues, though more complicated, characterizations of the case where the sparsity order is at most 2, which are different for $mathbbR$ and $mathbbC$. The existing proof for the complex case, is based on the result for the real case. In this paper we provide a more elementary proof of the characterization of the graphs whose complex sparsity order is at most two. Part of our proof relies on a characterization of the $P_4,overline{K}_3$-free graphs, with $P_4$ the path of length 3 and $overline{K}_3$ the stable set of cardinality 3, and of the class of clique-sums of such graphs.

Recommendations

• On the sparsity order of a graph and its deficiency in chordality
• scientific article; zbMATH DE number 4095519
• Positive semidefinite matrices with a given sparsity pattern
• Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors
• Sparse matrix decompositions and graph characterizations

Cites work

• scientific article; zbMATH DE number 4095519 (Why is no real title available?)
• A non-existence result on cyclic cycle-decompositions of the cocktail party graph
• Axiomatic characterization of the median and antimedian functions on cocktail-party graphs and complete graphs
• Clique partitions of the cocktail party graph
• Dihedral Hamiltonian cycle systems of the cocktail party graph
• Graph Classes: A Survey
• Matrix completions, moments, and sums of Hermitian squares
• On Majorization, Factorization, and Range Inclusion of Operators on Hilbert Space
• On rigid circuit graphs
• On the sparsity order of a graph and its deficiency in chordality
• Positive definite completions of partial Hermitian matrices
• Positive semidefinite matrices with a given sparsity pattern
• The Ranks of Extremal Positive Semidefinite Matrices with Given Sparsity Pattern

Cited in

(2)

• scientific article; zbMATH DE number 4095519 (Why is no real title available?)
• On the sparsity order of a graph and its deficiency in chordality

This page was built for publication: Graphs with sparsity order at most two: the complex case

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