ABSTRACT
Part of the beauty of, and fascination with, basic subset problems, such as the problems of finding the minimum cardinality of a dominating set and the maximum cardinality of an independent set, lies in the simplicity of their statements. (This simplicity is deceptive. For example, evaluating -y( G) is computationally difficult (that is, N P-hard) whereas in its continuous form, the corresponding linear programming problem can be solved in polynomial time.) However, as illustrated by Theorem 4.25, which states that
p(G):::; Pt(G) = -r1(G):::; -y(G):::; F(G):::; F1(G) = W1(G):::; W(G):::; n $ P(G) $ P1(G) = R1(G) $ R(G),
the determination of the values of fractional parameters can be useful not only for their own applications, but also in providing information about the related integer-valued parameters. For the fractional parameters in Chapter 4, we considered functions f: V(G)-+ [0,1), while for subset parameters like -y,p,F, and R, we can identify a subset S s; V(G) with its characteristic function ifJ : V (G) -+ { 0, 1}. Recall that for parameters W and P, we consider functions f: V(G)-+ {0,1,2,3, ... }. This chapter is concerned with the general case of Y-valued functions f: V(G)-+ Y for an arbitrary subset Y of the reals, Y s; ~.
