On hereditary subdirectly irreducible graphs. (English) Zbl 0567.05045

Let \({\mathcal C}\) be a class of loopless directed graphs closed under the categorical product (conjunction) \(\Pi\) and under taking induced subgraphs. A graph \(G\in {\mathcal C}\) is \({\mathcal C}\)-subdirectly irreducible if it satisfies the following condition: whenever G is isomorphic to an induced subgraph G’ of \(\prod_{i\in I}H_ i\) with each \(H_ i\in {\mathcal C}\) (i\(\in I)\) such that \(p_ i(G')=H_ i\) for all projections \(p_ i\), \(i\in I\), there exists a \(j\in I\) such that the restriction of \(p_ j\) to G’ is an isomorphism onto \(H_ j\). This paper contains a description of all classes \({\mathcal C}\) of graphs for which the property of \({\mathcal C}\)-subdirect irreducibility is hereditary, i.e., for which the class of \({\mathcal C}\)-subdirectly irreducible graphs is closed under taking induced subgraphs. A similar description for loopless undirected graphs was given earlier by the same author (Abstracta Eight Winter School on Abstract Analysis, Praha 1980, 180-193; cf. also Rep. ZW 193/83, Math. Centrum Amsterdam 1983). Subdirectly irreducible graphs were also studied by B. Fawcett (Ph.D. thesis, McMaster Univ. 1060), G. Sabidussi [Infinite finite sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. János Bolyai 10, 1199-1226 (1975; Zbl 0308.05124)] and the reviewer [ibid., 857-866 (1975; Zbl 0308.05125)].
Reviewer: P.Hell


05C99 Graph theory
Full Text: EuDML