Accession Number:

ADA282914

Title:

Conditional Graph Completions

Descriptive Note:

Technical rept. Oct-Dec 1993

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

1994-05-01

Pagination or Media Count:

14.0

Abstract:

If G V, E is a simple graph of order p and size q, and if P is a property held by G, we say that G is P-completable if there is an ordering e1, e2,...,e sub p2-q of the edges of K sub p-G such that G sub k V, E U k sub i1 e sub i has property P for each k 1,2,...,p2-q. The sequence G sub k is called a P-completion sequence. If all graphs with property P are P- completable, we say that P is a completable property and that the class II of graphs with property P is a completion class. Of interest are conditional completion classes, i.e., classes for which not all orderings lead to completion sequences. We show that several familiar classes of graphs are conditional completion classes. Chordal graphs, Perfect graphs, Matrix completions

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE