A greedy partition lemma for directed domination

DOI10.1016/J.DISOPT.2011.03.003zbMATH Open1236.05142arXiv1010.2467OpenAlexW2081115772WikidataQ124792155 ScholiaQ124792155MaRDI QIDQ665996FDOQ665996

Authors: Yair Caro, Michael A. Henning 

Publication date: 7 March 2012

Published in: Discrete Optimization (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. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if $alpha$ denotes the independence number of a graph $G$, we show that $alphaleGamm{a}_d(G)lealpha(1+2ln(n/alpha))$.

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

Recommendations

• Directed domination in oriented graphs
• Independent domination in directed graphs
• Directed domination in oriented hypergraphs
• Game domination number
• scientific article; zbMATH DE number 1161297

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?)
• On independent generalized degrees and independence numbers in \(K(1,m)\)- free graphs
• On the ratio of optimal integral and fractional covers
• Title not available (Why is that?)
• Title not available (Why is that?)
• 25 pretty graph colouring problems
• On a Problem in Graph Theory
• Title not available (Why is that?)
• Directed domination in oriented graphs
• Dominating Set and Converse Dominating Set of a Directed Graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the out-domination and in-domination numbers of a digraph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Total and connected domination in digraphs
• Title not available (Why is that?)
• Decompositions of partially ordered sets into chains and antichains of given size
• Title not available (Why is that?)

Cited In (5)

• Orientable burning number of graphs
• Directed domination in oriented hypergraphs
• Domination in digraphs
• Projects in \((t,r)\) broadcast domination
• Directed domination in oriented graphs

This page was built for publication: A greedy partition lemma for directed domination

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