Partitioning a graph into convex sets. (English) Zbl 1223.05220

Summary: Let \(G\) be a finite simple graph. Let \(S \subseteq V(G)\), its closed interval \(I[S]\) is the set of all vertices lying on shortest paths between any pair of vertices of \(S\). The set \(S\) is convex if \(I[S]=S\). In this work we define the concept of a convex partition of graphs. If there exists a partition of \(V(G)\) into \(p\) convex sets we say that \(G\) is \(p\)-convex. We prove that it is \(NP\)-complete to decide whether a graph \(G\) is \(p\)-convex for a fixed integer \(p\geq 2\). We show that every connected chordal graph is \(p\)-convex, for \(1\leq p\leq n\). We also establish conditions on \(n\) and \(k\) to decide if the \(k\)-th power of a cycle \(C_{n}\) is \(p\)-convex. Finally, we develop a linear-time algorithm to decide if a cograph is \(p\)-convex.


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
Full Text: DOI


[1] Artigas, D.; Dourado, M.C.; Szwarcfiter, J.L., Convex partitions of graphs, Electronic notes on discrete mathematics, 29, 147-151, (2007), EuroComb’07—European Conference on Combinatorics, Graph Theory and Applications, Sevilla, Spain · Zbl 1341.05198
[2] Bondy, J.A.; Murty, U.S.R., Graph theory, (2008), Springer · Zbl 1134.05001
[3] Brandstädt, A.; Dragan, F.F.; Nicolai, F., Lexbfs-orderings and powers of chordal graphs, Discrete mathematics, 171, 27-42, (1997) · Zbl 0880.05074
[4] Cáceres, J.; Hernando, M.C.; Mora, M.; Pelayo, I.M.; Puertas, M.L.; Seara, C., On geodetic sets formed by boundary vertices, Discrete mathematics, 306, 2, 188-198, (2006) · Zbl 1084.05025
[5] Campos, C.N.; Dantas, S.; Mello, C.P., Colouring clique hypergraphs of circulant graphs, Electronic notes in discrete mathematics, 30, 189-194, (2008), LAGOS’07—IV Latin-American Graphs, Algorithms and Optimization Symposium, Puerto Varas, Chile · Zbl 1341.05065
[6] Campos, C.N.; de Mello, C.P., A result on the total colouring of power of cycles, Discrete applied mathematics, 155, 585-597, (2007) · Zbl 1124.05031
[7] Changat, M.; Mathew, J., On triangle path convexity in graphs, Discrete mathematics, 206, 91-95, (1999) · Zbl 0929.05046
[8] Chepoi, V., Separation of two convex sets in convexity structures, Journal of geometry, 50, 30-51, (1994) · Zbl 0807.52002
[9] Chepoi, V.D.; Soltan, V.P., Conditions for invariance of set diameters under \(d\)-convexification in a graph, Cybernetics and systems analysis, 19, 6, 750-756, (1983) · Zbl 0564.05037
[10] Corneil, D.G.; Lerchs, H.; Stewart Burlingham, L., Complement reducible graphs, Discrete applied mathematics, 3, 3, 163-174, (1981) · Zbl 0463.05057
[11] Corneil, D.G.; Perl, Y.; Stewart, L.K., A linear recognition algorithm for cographs, SIAM journal on computing, 14, 4, 926-934, (1985) · Zbl 0575.68065
[12] Dourado, M.C.; Gimbel, J.G.; Protti, F.; Szwarcfiter, J.L.; Kratochvíl, J., On the computation of the hull number of a graph, Discrete mathematics, 309, 5668-5674, (2009) · Zbl 1215.05184
[13] Dourado, M.C.; Protti, F.; Rautenbach, D.; Szwarcfiter, J.L., Some remarks on the geodetic number of a graph, Discrete mathematics, 310, 832-837, (2010) · Zbl 1209.05129
[14] Dourado, M.C.; Protti, F.; Szwarcfiter, J.L., Complexity results related to monophonic convexity, Discrete applied mathematics, 158, 1268-1274, (2010) · Zbl 1209.05130
[15] M.C. Dourado, F. Protti, J.L. Szwarcfiter, On the computation of some parameters related to convexity of graphs, in: Lecture Notes of the Ramanujan Mathematical Society, Bangalore, India, Proc. of Int. Conf. on Disc. Math., 2006, pp. 102-112.
[16] Edelman, P.H.; Jamison, R.E., The theory of convex geometries, Geometriae dedicata, 19, 247-270, (1985) · Zbl 0577.52001
[17] Erdős, P.; Fried, E.; Hajnal, A.; Milner, E.C., Some remarks on simple tournaments, Algebra universalis, 2, 238-245, (1972) · Zbl 0267.05104
[18] Farber, M.; Jamison, R.E., Convexity in graphs and hypergraphs, SIAM journal on algebraic and discrete methods, 7, 433-444, (1986) · Zbl 0591.05056
[19] Farber, M.; Jamison, R.E., On local convexity in graphs, Discrete mathematics, 66, 231-247, (1987) · Zbl 0619.05032
[20] Golumbic, M.C.; Hammer, P.L., Stability in circular arc graphs, Journal of algorithms, 9, 3, 314-320, (1988) · Zbl 0651.68083
[21] Harary, F.; Nieminen, J., Convexity in graphs, Journal of differential geometry, 16, 185-190, (1981) · Zbl 0493.05037
[22] M. Lin, D. Rautenbach, F. Soulignac, J.L. Szwarcfiter, On powers of cycles, powers of paths and their induced subgraphs, Manuscript, 2007.
[23] Thomassen, C., Some remarks on hajós’ conjecture, Journal of combinatorial theory, series B, 93, 95-105, (2005) · Zbl 1061.05040
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.