Minimal hereditary dominating pair graphs
Nataša Pržulj · Library and Archives Canada (Government of Canada) · 2000
This 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 fx; y; zg, and satisfies the following: if P c a;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 P z x;y [ P y x;z [P x y;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.