Czasopismo
Tytuł artykułu
Warianty tytułu
Języki publikacji
Abstrakty
An abstract convexity space on a connected hypergraph H with vertex set V (H) is a family C of subsets of V (H) (to be called the convex sets of H) such that: (i) C contains the empty set and V (H), (ii) C is closed under intersection, and (iii) every set in C is connected in H. A convex set X of H is a minimal vertex convex separator of H if there exist two vertices of H that are separated by X and are not separated by any convex set that is a proper subset of X. A nonempty subset X of V (H) is a cluster of H if in H every two vertices in X are not separated by any convex set. The cluster hypergraph of H is the hypergraph with vertex set V (H) whose edges are the maximal clusters of H. A convexity space on H is called decomposable if it satisfies the following three properties: (C1) the cluster hypergraph of H is acyclic, (C2) every edge of the cluster hypergraph of H is convex, (C3) for every nonempty proper subset X of V (H), a vertex v does not belong to the convex hull of X if and only if v is separated from X in H by a convex cluster. It is known that the monophonic convexity (i.e., the convexity induced by the set of chordless paths) on a connected hypergraph is decomposable. In this paper we first provide two characterizations of decomposable convexities and then, after introducing the notion of a hereditary path family in a connected hypergraph H, we show that the convexity space on H induced by any hereditary path family containing all chordless paths (such as the families of simple paths and of all paths) is decomposable.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
493-515
Opis fizyczny
Daty
wydano
2015-08-01
otrzymano
2014-01-20
poprawiono
2014-10-07
zaakceptowano
2014-10-23
online
2015-07-29
Twórcy
- Department of Informatics Sapienza University of Rome Via Salaria 113, 00198 Roma, Italy, malvestuto@di.uniroma1.it
autor
- Department of Informatics Sapienza University of Rome Via Salaria 113, 00198 Roma, Italy, moscarini@di.uniroma1.it
Bibliografia
- [1] C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirability of acyclic database schemes, J. ACM 30 (1983) 479-513. doi:10.1145/2402.322389[Crossref]
- [2] M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999) 91-95. doi:10.1016/S0012-365X(98)00394-X[Crossref]
- [3] M. Changat, H.M. Mulder and G. Sierksma, Convexities related to path properties on graphs, Discrete Math. 290 (2005) 117-131. doi:10.1016/j.disc.2003.07.014[Crossref]
- [4] R. Diestel, Graph Decompositions: A Study in Infinity Graph Theory (Clarendon Press, Oxford, 1990).
- [5] P. Duchet, Convexity in combinatorial structures, in: Proceedings of the 14th Winter School on Abstract Analysis, Frolik, Souček and Fabián (Eds), (Circolo Matematico di Palermo, Palermo 1987), Serie II 14 261-293
- [6] P. Duchet, Convex sets in graphs II: minimal path convexity, J. Combin. Theory Ser. B 44 (1988) 307-316. doi:10.1016/0095-8956(88)90039-1[Crossref]
- [7] P. Duchet, Discrete convexity: retractions, morphisms and the partition problem, in: Proceedings of the Conference on Graph Connections, Balakrishnan, Mulder and Vijayakumar (Ed(s)), (Allied Publishers, New Delhi, 1999) 10-18.
- [8] M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Alge- braic Discrete Methods 7 (1986) 433-444. doi:10.1137/0607049[Crossref]
- [9] H.-G. Leimer, Optimal decomposition by clique separators, Discrete Math. 113 (1993) 99-123. doi:10.1016/0012-365X(93)90510-Z[Crossref]
- [10] F.M. Malvestuto, Canonical and monophonic convexities in hypergraphs, Discrete Math. 309 (2009) 4287-4298. doi:10.1016/j.disc.2009.01.003[Crossref][WoS]
- [11] F.M. Malvestuto, Decomposable convexities in graphs and hypergraphs, ISRN Com- binatorics 2013 Article ID 453808. doi:10.1155/2013/453808[Crossref]
- [12] F.M. Malvestuto, M. Mezzini and M. Moscarini, Equivalence between hypergraph convexities ISRN Discrete Mathematics 2011 Article ID 806193. doi:10.5402/2011/806193[Crossref]
- [13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2[Crossref]
- [14] M. Van de Vel, Theory of Convex Structures (North-Holland Publishing Co., Ams- terdam, 1993).
- [15] S. Whitesides, An Algorithm for finding clique cut-sets, Inform. Process. Lett. 12 (1981) 31-32. doi:10.1016/0020-0190(81)90072-7 [Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1815