×

Critically twin primitive 2-structures. (English) Zbl 1327.05286

Summary: Unlike graphs, digraphs or binary relational structures, the 2-structures do not define precise links between vertices. They only yield an equivalence between links. Also 2-structures provide a suitable generalization in the framework of clan decomposition. Let \(\sigma\) be a 2-structure. A subset \(C\) of \(V(\sigma)\) is a clan of \(\sigma\) if for each \(v\in V(\sigma)\setminus C\), \(v\) is linked in the same way to all the elements of \(C\). A 2-structure \(\sigma\) is clan primitive if \(|V(\sigma)|\geq 3\) and all its clans are trivial. A clan primitive 2-structure \(\sigma\) is critically primitive if \(\sigma[V(\sigma)\setminus\{v\}]\) is not primitive for every \(v\in V(\sigma)\). A clan of cardinality 2 is a twin pair. A 2-structure \(\sigma\) is twin primitive if \(|V(\sigma)|\geq 3\) and \(\sigma\) has no twin pairs. A twin primitive 2-structure \(\sigma\) is critically twin primitive if \(\sigma [V(\sigma)\setminus\{v\}]\) is not twin primitive for every \(v\in V(\sigma)\). First, a twin decomposition is provided for 2-structures. Second, twin primitivity is studied by proving analogues of results on clan primitivity. Third, the notion of critically closed subset is introduced to characterize critically twin primitive 2-structures.

MSC:

05C75 Structural characterization of families of graphs
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI

References:

[1] Birnbaum, Z.W., Esary, J.D.: Modules of coherent binary systems. J. Soc. Ind. Appl. Math. 13, 444-462 (1965) · Zbl 0235.94029 · doi:10.1137/0113027
[2] Bonizzoni, P.: Primitive 2-structures with the (n-2)-property. Theor. Comput. Sci. 132, 151-178 (1994) · Zbl 0822.68078 · doi:10.1016/0304-3975(94)90231-3
[3] Boudabbous, I., Ille, P.: Critical and infinite directed graphs. Discret. Math. 307, 2415-2428 (2007) · Zbl 1155.05327 · doi:10.1016/j.disc.2006.10.015
[4] Boudabbous, Y., Ille, P.: Indecomposability graph and critical vertices of an indecomposable graph. Discret. Math. 309, 2839-2846 (2009) · Zbl 1182.05062 · doi:10.1016/j.disc.2008.07.015
[5] Boudabbous, Y., Salhi, A.: Les graphes critiquement sans duo. C. R. Acad. Sci. Paris 347, 463-466 (2009) · Zbl 1168.05032 · doi:10.1016/j.crma.2009.03.008
[6] Burley, M., Uhry, J.P.: Parity graphs. Ann. Discret. Math. 16, 1-26 (1982) · Zbl 0496.05044
[7] Cournier, A., Ille, P.: Minimal indecomposable graphs. Discret. Math. 183, 61-80 (1998) · Zbl 0897.05070 · doi:10.1016/S0012-365X(97)00077-0
[8] Culus, J.-F., Jouve, B.: Convex circuit-free coloration of an oriented graph. European J. Comb. 30, 43-52 (2009) · Zbl 1213.05073 · doi:10.1016/j.ejc.2008.02.012
[9] Ehrenfeucht, A., Harju, T., Rozenberg, G.: The Theory of 2-Structures. A Framework for Decomposition and Transformation of Graphs. World Scientific, Singapore (1999) · Zbl 0981.05002 · doi:10.1142/4197
[10] Fraïssé, R.: On a decomposition of relations which generalizes the sum of ordering relations. Bull. Am. Math. Soc. 59, 389 (1953)
[11] Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18, 25-66 (1967) · Zbl 0153.26002 · doi:10.1007/BF02020961
[12] Godsil, C.D., Kocay, W.L.: Constructing graphs with pairs of pseudo-similar vertices. J. Comb. Theory Ser. B 32, 146-155 (1982) · Zbl 0465.05059 · doi:10.1016/0095-8956(82)90030-2
[13] Ille, P.; Sands, B. (ed.); Sauer, N. (ed.); Woodrow, R. (ed.), Recognition problem in reconstruction for decomposable relations, 189-198 (1993), Dordrecht · Zbl 0845.04002 · doi:10.1007/978-94-011-2080-7_13
[14] Ille, P.: La décomposition intervallaire des structures binaires. La Gazette des Mathématiciens 104, 39-58 (2005) · Zbl 1154.03309
[15] Maffray, F.; Preissmann, M.; Ramirez-Alfonsin, JL (ed.); Reed, BA (ed.), A translation of Tibor Gallai’s paper: Transitiv orientierbare Graphen, 25-66 (2001), New York · Zbl 0989.05050
[16] Möhring, R.H.: Algorithmic aspects of the substitution decomposition in optimization over relations, sets systems and Boolean functions. Ann. Oper. Res. 4, 195-225 (1985) · doi:10.1007/BF02022041
[17] Prins, G.: The automorphism group of a tree. Ph.D. thesis, University of Michigan (1957) · Zbl 0077.20104
[18] Sabidussi, G.: The composition of graphs. Duke Math. J. 26, 693-696 (1959) · Zbl 0095.37802 · doi:10.1215/S0012-7094-59-02667-5
[19] Schmerl, J.H., Trotter, W.T.: Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discret. Math. 113, 191-205 (1993) · Zbl 0776.06002 · doi:10.1016/0012-365X(93)90516-V
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.