×

Primitive 2-structures with the \((n-2)\)-property. (English) Zbl 0822.68078

Summary: A fundamental notion in the theory of 2-structures is that of a primitive 2-structure. A. Ehrenfeucht and G. Rozenberg [Theor. Comput. Sci. 70, No. 3, 343-358 (1990; Zbl 0701.05053)]proved that primitivity is hereditary in the sense that each primitive 2-structure on \(n\) elements, where \(n \geq 3\), contains a primitive substructure on either \(n - 1\) or \(n - 2\) elements. In this paper we determine the class of primitive 2-structures on \(n\) elements that do not contain primitive substructures on \(n - 1\) elements: these 2-structures are said to satisfy the \((n - 2)\)-property. We show that for each \(n > 3\), there is a restricted number of primitive 2-structures on \(n\) elements satisfying this property In fact, for each \(n > 4\), there are four different reversible 2-structures up to isomorphism, satisfying the \((n - 2)\)- property, while for \(n\) odd, there are five different 2-structures with this property.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory

Citations:

Zbl 0701.05053
Full Text: DOI

References:

[1] Bonizzoni, P., Primitivity in 2-structures and graphs, (Ph.D. Thesis (1992), Universitàdegli Studi di Milano, Dipartimento di Scienze della Informazione: Universitàdegli Studi di Milano, Dipartimento di Scienze della Informazione Milan) · Zbl 1418.68163
[2] Ehrenfeucht, A.; Rozenberg, G., Partial 2-structures, part II: state spaces of concurrent systems, Acta Informatica, 27, 348-368 (1990) · Zbl 0696.68083
[3] Ehrenfeucht, A.; Rozenberg, G., Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., 70, 343-358 (1990) · Zbl 0701.05053
[4] Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, part I: clans, basic subclasses and morphisms, Theoret. Comput. Sci., 70, 277-303 (1990) · Zbl 0701.05051
[5] Ehrenfeucht, A.; Rozenberg, G., Theory of 2-structures, part II: representation through labeled tree families, Theoret. Comput. Sci., 70, 305-342 (1990) · Zbl 0701.05052
[6] Ehrenfeucht, A.; Rozenberg, G., Angular 2-structures, Theoret. Comput. Sci., 92, 227-248 (1992) · Zbl 0753.05069
[7] Harju, T.; Rozenberg, G., Reductions for primitive 2-structures, manuscript (1992) · Zbl 0798.05068
[8] Moon, J. W., Topics on Tournaments (1968), Selected topics in Mathematics, Athena Series · Zbl 0191.22701
[9] Muller, J. H.; Spinrad, J., Incremental modular decomposition, J. ACM, 36, 1-19 (1989) · Zbl 0671.68030
[10] Spinrad, J., On comparability and permutation graphs, SIAM J. Comput., 14, 658-670 (1985) · Zbl 0568.68051
[11] Summer, D. P., Graphs indecomposable with respect to the X-join, Discrete Math., 6, 281-298 (1973) · Zbl 0279.05125
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.