Date of Graduation

2002

Document Type

Thesis

Degree Type

MS

Committee Chair

Elaine M. Eschen

Abstract

An n-term nonincreasing nonnegative integer sequence π = (d1, d2, · · · , dn) is said to be graphic if it is the degree sequence of a simple graph G of order n, and such graph G is referred to as a realization of π. Let H be a simple graph. A graphic sequence π is said to be potentially H-graphic if it has a realization G containing H as a subgraph. In this paper, we characterize the potentially (Kk − e)-graphic sequences for k = 4 and 5 where (Kk−e) is the graph obtained from Kk by removing one edge. This characterization implies a theorem due to C. H. Lai [15] and a characterization of potentially C4-graphic sequences due to R. Luo [20].

Download

Share

COinS