×

Convex sets in graphs. (English) Zbl 0967.05031

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\).

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite