Edge Annihilation Sequences for Classes of Chordal Graphs.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1996
- Accession Number
- ADA313817
Entities
People
- Thomas J Carroll
Organizations
- Naval Postgraduate School