On the computational complexity of upper fractional domination (Q753848): Difference between revisions

Two well-studied parameters of graphs are \(\gamma\) (G) and \(\Gamma\) (G), the minimum and maximum cardinality over all minimal dominating sets in G. The authors study a nondiscrete generalization of \(\Gamma\) (G): the maximum weight over all minimal dominating functions \(\Gamma_ f(G)\). They show that (1) \(\Gamma_ f(G)\) is computable and is always a rational number; (2) the decision problems corresponding to the problems of computing \(\Gamma\) (G) and \(\Gamma_ f(G)\) are NP-complete; (3) for trees \(\Gamma_ f(G)=\Gamma (G)\).