Chartrand, Gary; Zhang, Ping Convex sets in graphs. (English) Zbl 0967.05031 Congr. Numerantium 136, 19-32 (1999). Summary: 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\) geodesic in \(G\). For a set \(S\) of vertices of \(G\), the union of all sets \(I(u,v)\) for \(u,v\in S\) is denoted by \(I(S)\). A set \(S\) is convex if \(I(S)= S\). The convexity number \(\text{con}(G)\) is the maximum cardinality of a proper convex set of \(G\). A connected graph \(G\) is polyconvex if for every integer \(i\) with \(1\leq i\leq\text{con}(G)\), there exists a convex set of cardinality \(i\) in \(G\). Some well-known polyconvex and nonpolyconvex graphs are determined. It is shown that every pair \(k\), \(n\) of integers with \(2\leq k\leq n-1\) is realizable as the convexity number and order, respectively, of some connected polyconvex graph. Bounds for \(\text{con}(G)+\text{con}(\overline G)\) are discussed. In this connection, for positive integers \(s\), \(t\), the convex Ramsey number \(\text{cr}(s,t)\) is defined as the smallest positive integer \(n\) such that for every graph \(G\) of order \(n\), either \(G\) contains a maximum convex set of cardinality \(\geq s\) or \(\overline G\) contains a maximum convex set of cardinality \(\geq t\). Cited in 2 ReviewsCited in 7 Documents MSC: 05C12 Distance in graphs Keywords:convexity number; convex set; polyconvex graph; convex Ramsey number PDFBibTeX XMLCite \textit{G. Chartrand} and \textit{P. Zhang}, Congr. Numerantium 136, 19--32 (1999; Zbl 0967.05031)