Return to search

Graph Convexity and Vertex Orderings

In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X\{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis. / Graduate / 0405 / rachela@uvic.ca

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/5289
Date25 April 2014
CreatorsAnderson, Rachel Jean Selma
ContributorsOellermann, Ortrud R., MacGillivray, Gary
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0023 seconds