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