2 — Chordal Graphs
Scott McCullough · Birkhäuser Basel eBooks · 1988
Let P be an undirected graph with vertices V and edges E. Fix an enumeration, {v 1 ,v 2 ,...,v n }, of V and let M(P) = {A ∈ M n (ℂ)| = 0 if (v i ,v j ) ∉ E where e i is the standard orthonormal basis of ℂ n . M n (ℂ) + is the set of positive semi-definite n × n matrices with complex entries. For X ⊂ M n (ℂ) + a cone, define the order of X, denoted ord(X), to be the smallest integer k such that the elements of X of rank at most k generate X as a cone. For any set X, let M m (X) denote m x m matrices with entries from X. It is known that a graph P is chordal if and only if ord(M m (M(P)) + ) = 1 for every positive integer m, where M m (M(P)) + = {A ∈ M m (M(P))|A is positive semi-definite}. We characterize, in a graph theoretic way, graphs P for which ord(M m (M(P)) + ) = ord(M(P) + ) ≤ 2 for every positive integer m. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.