Convexity in oriented graphs (Q5957301)

From MaRDI portal





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
    0 references
    0 references
    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

    Identifiers