کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128259 | 1489492 | 2017 | 12 صفحه PDF | دانلود رایگان |
The domination number γ(G) of a graph G, its exponential domination number γe(G), and its porous exponential domination number γeâ(G) satisfy γeâ(G)â¤Î³e(G)â¤Î³(G). We contribute results about the gaps in these inequalities as well as the graphs for which some of the inequalities hold with equality. Relaxing the natural integer linear program whose optimum value is γeâ(G), we are led to the definition of the fractional porous exponential domination number γe,fâ(G) of a graph G. For a subcubic tree T of order n, we show γe,fâ(T)=n+26 and γe(T)â¤2γe,fâ(T). We characterize the two classes of subcubic trees T with γe(T)=γe,fâ(T) and γ(T)=γe(T), respectively. Using linear programming arguments, we establish several lower bounds on the fractional porous exponential domination number in more general settings.
Journal: Discrete Optimization - Volume 23, February 2017, Pages 81-92