Conditional graph completions
By: by Craig W. Rasmussen
Contributors: Naval Postgraduate School (U.S.). Dept. of Mathematics
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1994
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 10
Subjects: GRAPHS
Other titles: NPS-MA-94-005.
Description: 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 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.
Notes: Cover title.

"NPS-MA-94-005."

"Technical report for period October 1993 - December 1993."

AD A282 914.

Includes bibliographical references (p. 10)

aq/aq cc:9116 03/21/97.