On a Flow-Related Domination Problem

摘要

Let D be a digraph. For each vertex v ∈ V(D), let E~+(v) denote the set of arcs of D with tail v, and E~-(v) the set of arcs with head v. A function f from E to R~+, the set of all nonnegative real numbers, is called a flow of G if ∑_(e∈E~+(v)) f(e)=∑_(e∈E~-(v)) f(e) for all v ∈V(G).Tutte [8, 9] introduced the concept in the 1950's. A subset F of the arc set E(D) is called an edge control set if any two flows of D are equal whenever they are in F. An edge control set F is said to be minimal if any proper subset of F is no longer an edge control set of D. An edge control set F = {e_l,…, e_k} is said to be free if, for any nonnegative real numbers a_1,a_2,…, a_k, there always exists a flow f for D so that f(e_I) = a_I, for all i = 1,2,…,k. Let D be a digraph so that every arc is on a directed cycle. In this paper, we proved that a minimal edge control set F is free if and only if for each arc uv ∈ F there is a directed path from v to u in D -^sF. This implies that a minimal edge control set is free if and only if no two arcs in F are on a directed cycle of D. This flow-reflated domination problem was motivated by a traffic sensing problem [2] in transportation networks.