Structural conditions for cycle completable graphs

DOI10.1016/0012-365X(95)00107-8MaRDI QIDQ1126192zbMATH OpenFDO

Authors Charles R. Johnson, Terry A. McKee

Publication date 8 December 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00107-8

zbMATH Keywords

characterizationchordal graphcycle completable graphsdecompositionpositive definite matrixseries-parallel

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)

Review text

Cycle completable graphs appear in the characterization of partial real symmetric matrices for which there is a choice of the unspecified entries so as to make the given matrix positive definite. The authors characterize cycle completable graphs \(G\) by two equivalent conditions: (1) \(G\) has a cutclique decomposition into chordal and series-parallel pieces, and (2) \(G\) has a mixed elimination ordering (which is a generalization of the well-known perfect elimination ordering). From this result it is derived that cycle completable graphs can be recognized in \(O(nm)\) time.

Recommendations

• Cycle decompositions of complete graphs
• scientific article; zbMATH DE number 3950581
• scientific article; zbMATH DE number 819129
• New sufficient conditions for cycles in graphs
• Graphs constructible from cycles and complete graphs
• scientific article; zbMATH DE number 4127262
• An implicit degree condition for cyclability in graphs
• The structure of graphs with given lengths of cycles
• A sufficient condition for cyclability in directed graphs
• scientific article; zbMATH DE number 4106890

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• On the chordality of a graph
• Optimal decomposition by clique separators
• Positive definite completions of partial Hermitian matrices
• Series‐parallel graphs: A logical approach
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Euclidean distance completion problem: cycle completability
• The Euclidian Distance Matrix Completion Problem
• The real positive definite completion problem for a simple cycle
• The real positive definite completion problem: cycle completability
• Topology of series-parallel networks

Cited in

(11)

• Cuts, matrix completions and graph rigidity
• Maximum likelihood threshold and generic completion rank of graphs
• An efficient algorithm for maximum entropy extension of block-circulant covariance matrices
• Conditions for a totally positive completion in the case of a symmetrically placed cycle
• scientific article; zbMATH DE number 819129 (Why is no real title available?)
• scientific article; zbMATH DE number 841628 (Why is no real title available?)
• Sums of squares and sparse semidefinite programming
• Partial characterizations of 1-perfectly orientable graphs
• Singularity degree of the positive semidefinite matrix completion problem
• Characterizing and generalizing cycle completable graphs
• The real positive semidefinite completion problem for series-parallel graphs

This page was built for publication: Structural conditions for cycle completable graphs

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