Convex Partitions of Graphs |
| |
| Institution: | 1. COPPE-Sistemas, Universidade Federal do Rio de Janeiro, Brazil;2. DEMAT, Universidade Federal Rural do Rio de Janeiro and NCE, UFRJ, Brazil;3. Instituto de Matemática, NCE, and COPPE, Universidade Federal do Rio de Janeiro, Brazil;1. University of Kaiserslautern (Department of Mathematics), Kaiserslautern, Germany;2. Université Blaise Pascal (Clermont-Ferrand II, LIMOS), BP 10125, 63173 Aubière Cedex, France;1. Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil;1. Departament de Matemàtica, Universitat de Lleida, Spain;2. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Spain;3. School of Mathematical and Physical Sciences, University of Newcastle, Australia;4. Department of Mathematics, University of West Bohemia, Pilsen, Czech Republic;5. Department of Informatics, King’s College London, United Kingdom;6. Department of Mathematics, Institut Teknologi Bandung, Indonesia;1. Technische Universität Chemnitz, Germany;2. Universidade Federal do Rio Grande do Sul, Porto Alegre, Brazil |
| |
| Abstract: | A set of vertices S of a graph G is convex if all vertices of every geodesic between two of its vertices are in S. We say that G is k-convex if V(G) can be partitioned into k convex sets. The convex partition number of G is the least k ⩾ 2 for which G is k-convex. In this paper we examine k-convexity of graphs. We show that it is NP-complete to decide if G is k-convex, for any fixed k ⩾ 2. We describe a characterization for k-convex cographs, leading to a polynomial time algorithm to recognize if a cograph is k-convex. Finally, we discuss k-convexity for disconnected graphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
