Directed domination in oriented graphs

DOI10.1016/J.DAM.2011.12.027zbMATH Open1242.05198arXiv1010.2464OpenAlexW2041964508MaRDI QIDQ423913FDOQ423913

Yair Caro, Michael A. Henning

Publication date: 30 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A directed dominating set in a directed graph $D$ is a set $S$ of vertices of $V$ such that every vertex $uinV(D)setminusS$ has an adjacent vertex $v$ in $S$ with $v$ directed to $u$. The directed domination number of $D$, denoted by $gamma(D)$, is the minimum cardinality of a directed dominating set in $D$. The directed domination number of a graph $G$, denoted $Gamm{a}_d(G)$, which is the maximum directed domination number $gamma(D)$ over all orientations $D$ of $G$. The directed domination number of a complete graph was first studied by Erd"{o}s [Math. Gaz. 47 (1963), 220--222], albeit in disguised form. We extend this notion to directed domination of all graphs. If $alpha$ denotes the independence number of a graph $G$, we show that if $G$ is a bipartite graph, we show that $Gamm{a}_d(G)=alpha$. We present several lower and upper bounds on the directed domination number.

Full work available at URL: https://arxiv.org/abs/1010.2464

Recommendations

• Directed domination in oriented hypergraphs
• scientific article; zbMATH DE number 1161338
• scientific article; zbMATH DE number 1161297
• Graph orientation and its total efficient domination
• Stratified domination in oriented graphs
• Dominating sets in directed graphs
• scientific article
• Bounds on the domination number in oriented graphs
• Efficient domination of the orientations of a graph
• scientific article; zbMATH DE number 1124608

zbMATH Keywords

oriented graphindependence numberdirected domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Small transversals in hypergraphs
• Transversal numbers of uniform hypergraphs
• On the degrees of the vertices of a directed graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a Problem in Graph Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dominating Set and Converse Dominating Set of a Directed Graph
• Tight lower bounds on the size of a maximum matching in a regular graph
• Title not available (Why is that?)
• An inequality for the chromatic number of a graph
• On the out-domination and in-domination numbers of a digraph
• Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A greedy partition lemma for directed domination
• A note on graphs which have upper irredundance equal to independence

Cited In (22)

• On the sum of the total domination numbers of a digraph and its converse
• Total Roman domination on the digraphs
• Orientable burning number of graphs
• Title not available (Why is that?)
• Directed domination in oriented hypergraphs
• Projects in (t, r) Broadcast Domination
• A note on Roman domination of digraphs
• Bounds on the signed Roman \(k\)-domination number of a digraph
• A greedy partition lemma for directed domination
• A note on lower bounds for the total domination number of digraphs
• Orientable domination in product-like graphs
• Oriented Forests in Directed Graphs
• Double Roman domination in digraphs
• Distance domination of generalized de Bruijn and Kautz digraphs
• Bounds on the domination number of a digraph
• On the rainbow domination number of digraphs
• Domination in Digraphs
• Dominating Set and Converse Dominating Set of a Directed Graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locating-dominating sets: from graphs to oriented graphs
• Constructing the minimum dominating sets of generalized de Bruijn digraphs

This page was built for publication: Directed domination in oriented graphs

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