Minimal and maximal \(e=1\) functions (Q2721327)

A function \(f\) on the vertex set \(V\) of a graph \(G\) with values in \([0,1]\) is an \(e=1\) function, if \(f(u)=1\) for all isolated vertices \(u\) of \(G\) and for each non-isolated vertex \(u\) of \(G\) there is some neighbour \(v\) such that \(f(u)+f(v)=1\). An \(e=1\) function is minimal (maximal) if decreasing (increasing) its values for some vertices can never result in another \(e=1\) function. The authors study the infimum and supremum of the weight \(\sum_{u\in V}f(u)\) of \(e=1\) functions and of minimal and maximal \(e=1\) functions. They relate these weights to some classical graph parameters (domination, vertex cover), discuss realization problems and determine the asymptotic behaviour of the infimum of the weight of a maximal \(e=1\) function for the path. They close with some open problems.