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.

05C99 Graph theory
90C10 Integer programming