Geodesic
Domination and fractional domination in digraphs
Ararat Harutyunyan1 ; Tien-Nam Le2 ; Alantha Newman3 ; Stéphan Thomasse2
1University of Paris-Dauphine
2ENS Lyon
3G-SCOP, Grenoble
The electronic journal of combinatorics, Tome 25 (2018) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/7211
Classification : 05C20, 05C69
Mots-clés : graphs and digraphs, domination, fractional domination

Ararat Harutyunyan  1   ; Tien-Nam Le  2   ; Alantha Newman  3   ; Stéphan Thomasse  2

1 University of Paris-Dauphine
2 ENS Lyon
3 G-SCOP, Grenoble 
@article{10_37236_7211,
     author = {Ararat Harutyunyan and Tien-Nam Le and Alantha Newman and St\'ephan Thomasse},
     title = {Domination and fractional domination in digraphs},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {3},
     doi = {10.37236/7211},
     zbl = {1395.05069},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7211/}
}
TY  - JOUR
AU  - Ararat Harutyunyan
AU  - Tien-Nam Le
AU  - Alantha Newman
AU  - Stéphan Thomasse
TI  - Domination and fractional domination in digraphs
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7211/
DO  - 10.37236/7211
ID  - 10_37236_7211
ER  - 
%0 Journal Article
%A Ararat Harutyunyan
%A Tien-Nam Le
%A Alantha Newman
%A Stéphan Thomasse
%T Domination and fractional domination in digraphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7211/
%R 10.37236/7211
%F 10_37236_7211
Ararat Harutyunyan; Tien-Nam Le; Alantha Newman; Stéphan Thomasse. Domination and fractional domination in digraphs. The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/7211

Cité par Sources :