Conditional Graph Completions
Craig W. Rasmussen · 1994
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 d, e2, . . . , e(p)_g of the edges of Kv- G such that Gk = (V, E + Uf=i Ct) has property P for each k- 1,2, . . . , Q- q. The sequence {Gk} 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 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