Graphs with sparsity order at most two: the complex case. Issue 12 (2nd December 2017)

• Record Type: Journal Article
• Authors: ter Horst, S.; Klem, E. M.
• Is Part Of: Linear & multilinear algebra. Volume 65:Issue 12(2017)
• Page Start: 2367
• Page End: 2386
• Publication Date: 2017-12-02
• Subjects: Sparsity order -- matrix cones -- forbidden subgraphs; Primary: 05C75 -- Secondary: 05C50 -- 47L07 -- 15B57; Algebras, Linear -- Periodicals; Multilinear algebra -- Periodicals; 512.505
• DOI: 10.1080/03081087.2016.1274362
• Languages: English
• ISSNs: 0308-1087

Abstract

Abstract: The sparsity order of a (simple undirected) graph is the highest possible rank (over or ) 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 and ) 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 and . 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 -free graphs, with the path of length 3 and the stable set of cardinality 3, and of the class of clique-sums of such graphs.