×

The convexity number of a graph. (English) Zbl 1002.05018

Let \(I[u,v]\) be the set consisting of all the vertices lying on a shortest path between two vertices \(u\) and \(v\) of a connected graph \(G\). Also, let \(I[S]\) be the union of all the sets \(I[u,v]\) for \(u\) and \(v\) in a subset \(S\) of the vertex set of \(G\). A set \(S\) is said to be convex if \(I[S]= S\). The convexity number \(\text{con}(G)\) is the maximum cardinality of a proper convex set of \(G\). The clique number \(\omega(G)\) is the maximum cardinality of a clique of \(G\). It is shown that for every triple \(l\), \(k\), \(n\) of integers with \(n\geq 3\) and \(2\leq l\leq k\leq n-1\), there exists a non-complete connected graph \(G\) of order \(n\) with \(\omega(G)= l\) and \(\text{con}(G)= k\).

MSC:

05C12 Distance in graphs
Full Text: DOI