Characterizing and generalizing cycle completable graphs

DOI10.1016/J.DISC.2023.113754arXiv2304.09335OpenAlexW4387806343MaRDI QIDQ6184532FDOQ6184532

Authors: Maria Chudnovsky, Ian M. J. McInnis 

Publication date: 25 January 2024

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

Abstract: The family of cycle completable graphs has several cryptomorphic descriptions, the equivalence of which has heretofore been proven by a laborious implication-cycle that detours through a motivating matrix completion problem. We give a concise proof, partially by introducing a new characterization. Then we generalize this family to ``$k$-quasichordal graphs, with three natural characterizations.

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

Recommendations

• Structural conditions for cycle completable graphs
• Characterization of completely positive graphs
• The real positive definite completion problem: cycle completability
• scientific article; zbMATH DE number 841628
• When every k-cycle has at least f(k) chords

zbMATH Keywords

forbidden induced subgraphs\(k\)-quasichordalcycle completable

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrix completion problems (15A83) Paths and cycles (05C38)

Cites Work

• On graphs with no induced subdivision of \(K_4\)
• S-functions for graphs
• Graph minors. III. Planar tree-width
• The real positive definite completion problem: cycle completability
• Contribution to nonserial dynamic programming
• Structural conditions for cycle completable graphs
• The Euclidean distance completion problem: cycle completability
• Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree

This page was built for publication: Characterizing and generalizing cycle completable graphs

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