Duality in graph families (Q1208357): Difference between revisions

The authors investigate some properties of collections of graphs called families. The complete graph family \({\mathcal C}\) is defined as a class of graphs which contains the one-vertex graph \(K_ 1\), is closed under contraction, and satisfies the following condition: \[ \text{if for a subgraph } H\text{ of } G, \quad H\in{\mathcal C},\quad G/H\in{\mathcal C}\text{ then also } G\in{\mathcal C}; \] where \(G/H\) is a contraction of \(G\) with respect to \(H\). A graph family \({\mathcal F}\) is free if it contains \(K_ 1\), is closed under subgraphs, and satisfies the following condition: \[ \text{if for any induced subgraph } H\text{ of } G,\;H\in{\mathcal F},\;G/H\in{\mathcal F}\text{ then also } G\in{\mathcal F}. \] The paper contains several characterization theorems for complete families and free families closed under some supplementary conditions as edge-deletions, edge- contractions etc.