×

Complexity results related to monophonic convexity. (English) Zbl 1209.05130

Summary: The study of monophonic convexity is based on the family of induced paths of a graph. The closure of a subset \(X\) of vertices, in this case, contains every vertex \(v\) such that \(v\) belongs to some induced path linking two vertices of \(X\). Such a closure is called monophonic closure. Likewise, the convex hull of a subset is called monophonic convex hull. In this work we deal with the computational complexity of determining important convexity parameters, considered in the context of monophonic convexity. Given a graph \(G\), we focus on three parameters: the size of a maximum proper convex subset of \(G\) (\(m\)-convexity number); the size of a minimum subset whose closure is equal to \(V(G)\) (monophonic number); and the size of a minimum subset whose convex hull is equal to \(V(G)\) (\(m\)-hull number). We prove that the decision problems corresponding to the m-convexity and monophonic numbers are NP-complete, and we describe a polynomial time algorithm for computing the \(m\)-hull number of an arbitrary graph.

MSC:

05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atici, M., Computational complexity of geodetic set, Int. J. Comput. Math., 79, 587-591 (2002) · Zbl 0999.05027
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory, Graduate Texts in Mathematics (2008), Springer · Zbl 1134.05001
[3] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, On monophonic sets in graphs, in: 20th British Combinatorial Conference, Durham, England, 2005; J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, On monophonic sets in graphs, in: 20th British Combinatorial Conference, Durham, England, 2005 · Zbl 1182.05050
[4] Changat, M.; Mulder, H. M.; Sierksma, G., Convexities related to path properties on graphs, Discrete Math., 290, 117-131 (2005) · Zbl 1058.05043
[5] Chepoi, V., Separation of two convex sets in convexity structures, J. Geom., 50, 30-51 (1994) · Zbl 0807.52002
[6] Dourado, M. C.; Gimbel, J. G.; Kratochvíl, J.; Protti, F.; Szwarcfiter, J. L., On the computation of the hull number of a graph, Discrete Math., 309, 5668-5674 (2009) · Zbl 1215.05184
[7] M.C. Dourado, F. Protti, D. Rautenbach, J.L. Szwarcfiter, On the convexity number of graphs, 2009 (submitted for publication); M.C. Dourado, F. Protti, D. Rautenbach, J.L. Szwarcfiter, On the convexity number of graphs, 2009 (submitted for publication) · Zbl 1207.05044
[8] M.C. Dourado, F. Protti, D. Rautenbach, J.L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Math. (2009) (in press); M.C. Dourado, F. Protti, D. Rautenbach, J.L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Math. (2009) (in press) · Zbl 1209.05129
[9] Dourado, M. C.; Protti, F.; Szwarcfiter, J. L., On the complexity of the geodetic and convexity numbers of a graph, (Proceedings of the International Conference on Discrete Mathematics. Proceedings of the International Conference on Discrete Mathematics, RMS Lecture Notes Series, vol. 7 (2006), Ramanujan Mathematical Society), 101-108 · Zbl 1168.05033
[10] Duchet, P., Convex sets in graphs II. Minimal path convexity, J. Comb. Theory Ser. B, 44, 307-316 (1988) · Zbl 0672.52001
[11] Edelman, P. H.; Jamison, R. E., The theory of convex geometries, Geometriae Dedicata, 19, 247-270 (1985) · Zbl 0577.52001
[12] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Alg. Disc. Meth., 7, 433-444 (1986) · Zbl 0591.05056
[13] Farber, M.; Jamison, R. E., On local convexity in graphs, Discrete Math., 66, 3, 231-247 (1987) · Zbl 0619.05032
[14] Gavril, F., Algorithms on clique separable graphs, Discrete Math., 19, 159-165 (1977) · Zbl 0378.05042
[15] Gimbel, J. G., Some remarks on the convexity number of a graph, Graphs Combin., 19, 357-361 (2003) · Zbl 1023.05079
[16] Haas, R.; Hoffmann, M., Chordless paths through three vertices, Theoret. Comput. Sci., 351, 360-371 (2006) · Zbl 1086.68102
[17] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, On geodesic and monophonic convexity, in: 20th European Workshop on Computational Geometry, Sevilla, Spain, 2004; C. Hernando, M. Mora, I.M. Pelayo, C. Seara, On geodesic and monophonic convexity, in: 20th European Workshop on Computational Geometry, Sevilla, Spain, 2004
[18] Jamison, R. E., A perspective on abstract convexity: Classifying alignments by varieties, (Kay, D. C.; Breen, M., Convexity and Related Combinatorial Geometry (1982), Marcel Dekker: Marcel Dekker New York) · Zbl 0482.52001
[19] Jamison, R. E.; Nowakovski, R., A Helly theorem for convexity in graphs, Discrete Math., 51, 35-39 (1984) · Zbl 0548.05052
[20] Karp, R., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-103 · Zbl 0366.68041
[21] I.M. Pelayo, Generalizing the Krein-Milman property in graph convexity spaces: A short survey, in: RMS Lecture Notes Series in Mathematics (in press); I.M. Pelayo, Generalizing the Krein-Milman property in graph convexity spaces: A short survey, in: RMS Lecture Notes Series in Mathematics (in press) · Zbl 1201.05067
[22] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[23] Whitesides, S. H., An algorithm for finding clique cut-sets, Inform. Process Lett., 12, 31-32 (1981) · 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.