×

Primitivity is hereditary for 2-structures. (English) Zbl 0701.05053

It is proved that each primitive 2-structure is built-up by adding one or two elements to a primitive 2-structure.
The importance of this fact follows from the fact that every 2-structure can be decomposed into primitive, complete and linear 2-structures. While linear and complete 2-structures have rather simple structure (they are much like linear orders and complete or totally disconnected graphs), the primitive 2-structures are difficult to understand.
Reviewer: M.Demlová

MSC:

05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L., Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057
[2] Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, Part I: clans, basic subclasses, and morphisms, Theoret. Comput. Sci., 70, 277-303 (1990), (this issue) · Zbl 0701.05051
[3] Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, Part II: representation through labeled tree families, Theoret. Comput. Sci., 70, 305-342 (1990), (this issue) · Zbl 0701.05052
[4] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[5] Seinsche, D., On a property of the class of \(n\)-colorable graphs, J. Combin. Theory Ser. B, 16, 191-193 (1974) · Zbl 0269.05103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.