scientific article; zbMATH DE number 1286753

From MaRDI portal
Publication:4243060





A domination parameter of a graph related to the possibilities of its orientation is introduced. For a directed graph \(D\) an open dominating set is a subset \(S\) of the vertex set of \(D\) such that each vertex of \(D\) either is in \(S\), or is the terminal vertex of an edge outgoing from a vertex of \(S\). The minimum number of vertices of an open dominating set of \(D\) is the open domination number \(\rho_1(D)\) of the directed graph \(D\). Now let \(G\) be an undirected graph. The minimum (or maximum) of open domination numbers of all orientations \(D\) of \(G\) is the lower (or upper, respectively) open domination number \(\text{dom}_1(G)\) (or \(\text{DOM}_1(G)\), respectively). It is proved that for a connected graph \(G\) these numbers exist if and only if \(G\) is not a tree. Some considerations on complete graphs are done. Among other results, it is proved that if \(c\) is an integer such that \(\text{dom}_1(K_n)\leq c\leq \text{DOM}_1(K_n)\), then there exists an orientation \(D\) of \(K_n\) such that \(\rho_1(D)=c\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4243060)