scientific article; zbMATH DE number 1286753
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\).
- Orientable domination in product-like graphs
- Efficient dominating sets in labeled rooted oriented trees
- Bounds on the domination number in oriented graphs
- Domination in digraphs
- scientific article; zbMATH DE number 1154593 (Why is no real title available?)
- scientific article; zbMATH DE number 1161297 (Why is no real title available?)
- scientific article; zbMATH DE number 1161338 (Why is no real title available?)
- Orientable total domination in graphs
- Characterization of graphs with orientable total domination number equal to \(|V| - 1\)
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)