Domination and Fractional Domination in Digraphs

Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, Stéphan Thomasse

Abstract


In this paper, we investigate the relation between the (fractional) domination number of a digraph $G$ and the independence number of its underlying graph, denoted by $\alpha(G)$. More precisely, we prove that every digraph $G$ on $n$ vertices has fractional domination number at most $2\alpha(G)$ and domination number at most $2\alpha(G) \cdot \log{n}$. Both bounds are sharp.


Keywords


Graphs and digraphs; Domination; Fractional domination

Full Text:

PDF