2017/08/01 by Ararat Harutyunyan, Tien-Nam Le, Harutyunyan, Ararat +5
Computer Science · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1708.00423
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 α(G). More precisely, we prove that every digraph G has fractional domination number at most 2α(G), and every directed triangle-free digraph G has domination number at most α(G)⋅ α(G)!. The first bound is sharp.