Structural conditions for cycle completable graphs

✍ Scribed by Charles R. Johnson; Terry A. McKee

• Book ID: 103061433
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 350 KB
• Volume: 159
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00107-8

✦ Synopsis

We first review the matrix completion problem that motivated cycle completable graphs. We then discuss prior and give new structural characterizations of these graphs, along with their relationship to chordal and series-parallel graphs.

The concept of cycle completable 9raph is introduced in [2] as a solution to a matrix completion problem. That solution involves the introduction of a new family of graphs larger than the family of chordal graphs. This new family is characterized below in Theorem 1 (taken from [-2]). We then prove additional structural characterizations of this new family and discuss related matters (including the complexity of recognition). One rather surprising observation is that this new family generalizes series-parallel graphs in much the same way that it generalizes chordal graphs.