Accession Number : ADA313817

Title :   Edge Annihilation Sequences for Classes of Chordal Graphs.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Carroll, Thomas

PDF Url : ADA313817

Report Date : JUN 1996

Pagination or Media Count : 57

Abstract : Given a non-empty graph G=(VE) of order n and size m, with some property P, we may ask whether there exists a sequence of graphs constructed by the sequential removal of edges e1, e2,...,em, with the property that if Go=G then (1) Gi is obtained from G(i-1) by deletion of exactly one edge and (2) Gi has property P for 1<i<m. We refer to such a sequence as an edge annihilation sequence. If G is chordal, strongly chordal, split, threshold, interval or unit interval, then we show that there exists an edge annihilation sequence for G. Algorithms and necessary vertex orderings are given for the construction of edge annihilation sequences for the above mentioned classes of graphs. We know that for G(n), the set of all labeled graphs G=(V,E) of order n, (G,<) is a partially ordered set (poset) under edge set inclusion. Using edge annihilation. sequences and edge completions sequences, we discuss the construction of a chain of graphs in G(n) with property P. We show that within G(n), every graph with property P lies on at least one chain of graphs with property P.

Descriptors :   *GRAPHS, *SET THEORY, *SEQUENCES(MATHEMATICS), ALGORITHMS, THESES, PERMUTATIONS, MAPPING(TRANSFORMATIONS).

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE