Characterizing and generalizing cycle completable graphs

DOI10.1016/J.DISC.2023.113754MaRDI QIDQ6184532zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Ian M. J. McInnis

Publication date 25 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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)