Abstract
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 )|\ge 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 )|\ge 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.
Similar content being viewed by others
References
Birnbaum, Z.W., Esary, J.D.: Modules of coherent binary systems. J. Soc. Ind. Appl. Math. 13, 444–462 (1965)
Bonizzoni, P.: Primitive 2-structures with the (n-2)-property. Theor. Comput. Sci. 132, 151–178 (1994)
Boudabbous, I., Ille, P.: Critical and infinite directed graphs. Discret. Math. 307, 2415–2428 (2007)
Boudabbous, Y., Ille, P.: Indecomposability graph and critical vertices of an indecomposable graph. Discret. Math. 309, 2839–2846 (2009)
Boudabbous, Y., Salhi, A.: Les graphes critiquement sans duo. C. R. Acad. Sci. Paris 347, 463–466 (2009)
Burley, M., Uhry, J.P.: Parity graphs. Ann. Discret. Math. 16, 1–26 (1982)
Cournier, A., Ille, P.: Minimal indecomposable graphs. Discret. Math. 183, 61–80 (1998)
Culus, J.-F., Jouve, B.: Convex circuit-free coloration of an oriented graph. European J. Comb. 30, 43–52 (2009)
Ehrenfeucht, A., Harju, T., Rozenberg, G.: The Theory of 2-Structures. A Framework for Decomposition and Transformation of Graphs. World Scientific, Singapore (1999)
Fraïssé, R.: On a decomposition of relations which generalizes the sum of ordering relations. Bull. Am. Math. Soc. 59, 389 (1953)
Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18, 25–66 (1967)
Godsil, C.D., Kocay, W.L.: Constructing graphs with pairs of pseudo-similar vertices. J. Comb. Theory Ser. B 32, 146–155 (1982)
Ille, P.: Recognition problem in reconstruction for decomposable relations. In: Sands, B., Sauer, N., Woodrow, R. (eds.) Finite and Infinite Combinatorics in Sets and Logic, pp. 189–198. Kluwer Academic Publishers, Dordrecht (1993)
Ille, P.: La décomposition intervallaire des structures binaires. La Gazette des Mathématiciens 104, 39–58 (2005)
Maffray, F., Preissmann, M.: A translation of Tibor Gallai’s paper: Transitiv orientierbare Graphen. In: Ramirez-Alfonsin, J.L., Reed, B.A. (eds.) Perfect Graphs, pp. 25–66. Wiley, New York (2001)
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)
Prins, G.: The automorphism group of a tree. Ph.D. thesis, University of Michigan (1957)
Sabidussi, G.: The composition of graphs. Duke Math. J. 26, 693–696 (1959)
Schmerl, J.H., Trotter, W.T.: Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discret. Math. 113, 191–205 (1993)
Acknowledgments
The authors thank R.E. Woodrow for his helpful comments. They also thank three referees for their constructive suggestions. One of them raises the problem of the infinite case that leads us to add the last section.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first Author would like to extend his sincere appreciation to the Deanship of Scientific Research at King Saud University for its funding of this research through the Research Group Project No RGP-VPP-056.
Rights and permissions
About this article
Cite this article
Boudabbous, Y., Ille, P., Jouve, B. et al. Critically Twin Primitive 2-Structures. Graphs and Combinatorics 31, 1223–1247 (2015). https://doi.org/10.1007/s00373-014-1436-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-014-1436-y