Conditional Graph Completions
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 (p/2)-q of the edges of K sub p-G such that G sub k = (V, E + U (k) sub i=1 e sub i) has property P for each k = 1,2,...,(p/2)-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
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1994
- Accession Number
- ADA282914
Entities
People
- Craig W. Rasmussen
Organizations
- Naval Postgraduate School