Define two graph properties P and Q to be hereditarily equivalent if, for every graph G, every induced subgraph of G satisfies P if and only if every induced subgraph of G satisfies Q. For instance, the properties 'every vertex has even degree,' 'the number of edges is even,' and 'edgeless' are hereditarily equivalent. This paper examines the graph metatheory of hereditary equivalence, including its intimate relationship to minimal equivalence and the resulting notion of complementary properties in the corresponding boolean algebra.
展开▼
