Structural conditions for cycle completable graphs

DOI10.1016/0012-365X(95)00107-8zbMath0861.05052MaRDI QIDQ1126192

Charles R. Johnson, Terry A. McKee

Publication date: 8 December 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

decompositioncharacterizationchordal graphpositive definite matrixseries-parallelcycle completable graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Related Items

Cuts, matrix completions and graph rigidity, Characterizing and generalizing cycle completable graphs, An efficient algorithm for maximum entropy extension of block-circulant covariance matrices, Maximum likelihood threshold and generic completion rank of graphs, The real positive semidefinite completion problem for series-parallel graphs, Sums of Squares and Sparse Semidefinite Programming, Singularity Degree of the Positive Semidefinite Matrix Completion Problem, Partial Characterizations of 1‐Perfectly Orientable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Positive definite completions of partial Hermitian matrices
• The real positive definite completion problem for a simple cycle
• Optimal decomposition by clique separators
• Topology of series-parallel networks
• Steiner trees, partial 2–trees, and minimum IFI networks
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Series‐parallel graphs: A logical approach
• On the chordality of a graph
• The Euclidian Distance Matrix Completion Problem
• The Euclidean distance completion problem: cycle completability
• The real positive definite completion problem: cycle completability