Minimal hereditary dominating pair graphs

grantor: University of TorontoThis thesis describes structural properties of 'hereditary dominating pair' ('HDP') and minimal HDP graphs. A ' dominating pair' ('DP') in a connected graph is a pair of vertices such that every path between them is dominating. A graph ' G' is HDP if every connected induced subgraph of 'G' has a DP. The class of HDP graphs includes all asteroidal triple-free (AT-free) graphs--already extensively studied--and some graphs containing asteroidal triples (ATs). A 'minimal' HDP graph 'H' contains an AT x,y,z , and satisfies the following: if Pca,b is the set of all induced paths between vertices 'a' and 'b' that avoid the neighborhood of a vertex 'c', then every vertex of 'H' belongs to a path in Pzx,y∪ Pyx,z∪P xy,z . The position of DP vertices in minimal HDP graphs is determined, as well as some structural properties dictated by the position of DP vertices.M.Sc