On the convexity number of graphs. (English) Zbl 1256.05123
Summary: A set of vertices \(S\) in a graph is convex if it contains all vertices which belong to shortest paths between vertices in \(S\). The convexity number \(c(G)\) of a graph \(G\) is the maximum cardinality of a convex set of vertices which does not contain all vertices of \(G\).
We prove NP-completeness of the problem to decide for a given bipartite graph \(G\) and an integer \(k\) whether \(c(G) \geq k\). Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.
We prove NP-completeness of the problem to decide for a given bipartite graph \(G\) and an integer \(k\) whether \(c(G) \geq k\). Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.
MSC:
| 05C38 | Paths and cycles |
| 05C35 | Extremal problems in graph theory |
| 05C12 | Distance in graphs |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. Siam Monogr. Discret. Math. (1999) · Zbl 0919.05001 |
| [2] | Cáceres J., Márquez A., Oellermann O.R., Puertas M.L.: Rebuilding convex sets in graphs. Discret. Math. 297, 26–37 (2005) · Zbl 1070.05035 · doi:10.1016/j.disc.2005.03.020 |
| [3] | Canoy S.R. Jr., Garces I.J.L.: Convex sets under some graph operations. Graphs Comb. 4, 787–793 (2002) · Zbl 1009.05054 |
| [4] | Chartrand G., Wall C.E., Zhang P.: The convexity number of a graph. Graphs Comb. 18, 209–217 (2002) · Zbl 1002.05018 · doi:10.1007/s003730200014 |
| [5] | Edelman P.H., Jamison R.E.: The theory of convex geometries. Geom. Dedicata. 19, 247–270 (1985) · Zbl 0577.52001 · doi:10.1007/BF00149365 |
| [6] | Farber M., Jamison R.E.: Convexity in graphs and hypergraphs. SIAM J. Algebraic Discret. Methods 7, 433–444 (1986) · Zbl 0591.05056 · doi:10.1137/0607049 |
| [7] | Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, New York (1979) · Zbl 0411.68039 |
| [8] | Gimbel J.G.: Some remarks on the convexity number of a graph. Graphs Comb. 19, 357–361 (2003) · Zbl 1023.05079 · doi:10.1007/s00373-002-0518-4 |
| [9] | Harary F., Nieminen J.: Convexity in graphs. J. Differ. Geom. 16, 185–190 (1981) · Zbl 0493.05037 |
| [10] | Kim B.K.: A lower bound for the convexity number of some graphs. J. Appl. Math. Comput. 14, 185–191 (2003) · Zbl 1035.05036 · doi:10.1007/BF02936107 |
| [11] | McConnell, R.M., Spinrad, J.P.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 536–545 (1994) · Zbl 0867.05068 |
| [12] | McConnell R.M., Spinrad J.P.: Ordered vertex partitioning. Discret. Math. Theor. Comput. Sci. 4, 45–60 (2000) · Zbl 0946.68101 |
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.
