Paper Info
Title
Relating domination, exponential domination, and porous exponential domination.
Abstract
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.
Year
DOI
Venue
2017
10.1016/j.disopt.2016.12.002
Discrete Optimization
Keywords
Field
DocType
Domination,Exponential domination,Porous exponential domination,Linear programming relaxation
Integer,Discrete mathematics,Graph,Combinatorics,Exponential function,Domination analysis,Mathematics
Journal
Volume
ISSN
Citations 
23
1572-5286
2
PageRank 
References 
Authors
0.47
4
3
Name
Order
Citations
PageRank
Michael A. Henning11865246.94
Simon Jäger220.81
Dieter Rautenbach3946138.87