×

Decomposability of abstract and path-induced convexities in hypergraphs. (English) Zbl 1317.05134

Summary: 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.

MSC:

05C65 Hypergraphs
52A01 Axiomatic and generalized convexity
52B55 Computational aspects related to convexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[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; · Zbl 0624.68087
[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; · Zbl 0929.05046
[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; · Zbl 1058.05043
[4] R. Diestel, Graph Decompositions: A Study in Infinity Graph Theory (Clarendon Press, Oxford, 1990).; · Zbl 0726.05001
[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; · Zbl 0644.52001
[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; · Zbl 0672.52001
[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.; · Zbl 0957.05030
[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; · Zbl 0591.05056
[9] H.-G. Leimer, Optimal decomposition by clique separators, Discrete Math. 113 (1993) 99-123. doi:10.1016/0012-365X(93)90510-Z; · Zbl 0793.05128
[10] F.M. Malvestuto, Canonical and monophonic convexities in hypergraphs, Discrete Math. 309 (2009) 4287-4298. doi:10.1016/j.disc.2009.01.003; · Zbl 1211.05093
[11] F.M. Malvestuto, Decomposable convexities in graphs and hypergraphs, ISRN Com- binatorics 2013 Article ID 453808. doi:10.1155/2013/453808; · Zbl 1264.05089
[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; · Zbl 1238.05186
[13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2;
[14] M. Van de Vel, Theory of Convex Structures (North-Holland Publishing Co., Ams- terdam, 1993).; · Zbl 0785.52001
[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; · Zbl 0454.68078
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.