# zbMATH — the first resource for mathematics

Fractional domination and fractional packing in graphs. (English) Zbl 0691.05043
Combinatorics, graph theory, and computing, Proc. 20th Southeast Conf., Boca Raton/FL (USA) 1989, Congr. Numerantium 71, 153-172 (1990).
Summary: [For the entire collection see Zbl 0688.00003.]
The fractional domination number of a graph $$G=(V,E)$$ has been defined to be $$\gamma_ f=\min \{\sum_{v\in V}g(v)\}$$ where g(v)$$\in [0,1]$$ and for each $$v\in V$$ the sum of the weights g(x) for $$x\in N[v]$$ is at least one. This is a modification of the domination number of G where g(v) would be required to be either 0 or 1. Here we introduce several similarly defined ”fractional parameters”. These include two whose 0-1 versions have been previously studied, namely packing (or strong stability) and efficient domination, and a third whose 0-1 version is a measure of ”redundance” (a concept which we introduce here).
We present illustrations of these parameters on several examples, their linear programming formulations, formulas for certain classes of graphs, and a discussion of bounds.

##### MSC:
 05C99 Graph theory 90C10 Integer programming