DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# Accession Number:

## ADA282914

# Title:

## Conditional Graph Completions

# Descriptive Note:

## Technical rept. Oct-Dec 1993

# Corporate Author:

## NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF MATHEMATICS

# 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

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#