Convexity in oriented graphs (Q5957301)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Convexity in oriented graphs |
scientific article; zbMATH DE number 1716683
Language | Label | Description | Also known as |
---|---|---|---|
English | Convexity in oriented graphs |
scientific article; zbMATH DE number 1716683 |
Statements
Convexity in oriented graphs (English)
0 references
3 July 2002
0 references
If \(V(G)\) is the vertex set of a connected oriented graph \(D\) then for two vertices \(u,v \in V(G)\) a shortest directed \(u\)-\(v\) path is called \(u\)-\(v\) geodesic. The closed interval \(I[u,v]\) consists of \(u\) and \(v\) together with all vertices lying in a \(u\)-\(v\) geodesic or in a \(v\)-\(u\) geodesic in \(D\). For \(S \subseteq V(D)\), \(I[S]\) is the union of all closed intervals \(I[u,v]\) with \(u,v \in S\). A set is convex if \(I[S]=S\). The convexity number con\((D)\) is the maximum cardinality of a proper convex set of \(V(D)\). It is proved that for any integers \(k\) and \(n\) satisfying the conditions \(1 \leq k \leq n-1\), \(k \not= 2\), and \(n \geq 4\), there exists a connected oriented graph of order \(n\) and convexity number \(k\). The lower (upper) orientable convexity number of a connected graph \(G\) is the minimum (maximum) convexity number among all orientations of \(G\). The lower orientable convexity numbers of some well-known graphs are determined, for example for outerplanar graphs.
0 references
convex set
0 references
convexity number
0 references
orientable convexity number
0 references