Abstract.
For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: August 19, 1998 Final version received: May 17, 2000
Rights and permissions
About this article
Cite this article
Chartrand, G., Wall, C. & Zhang, P. The Convexity Number of a Graph. Graphs Comb 18, 209–217 (2002). https://doi.org/10.1007/s003730200014
Issue Date:
DOI: https://doi.org/10.1007/s003730200014