Edge-weighted domination in graphs

In this paper, we consider an edge-weighted social system, in which every edge [Formula: see text] is associated with a number [Formula: see text] in [Formula: see text] representing the intimate degree between two people [Formula: see text] and [Formula: see text]. We want to find a team in this system, to control the whole system. Based on this background, we introduce a new type of domination as follows. A set [Formula: see text] is called an edge-weighted dominating set of [Formula: see text] if for every [Formula: see text], [Formula: see text]. The edge-weighted domination number of [Formula: see text] is the minimum cardinality among all edge-weighted dominating sets of [Formula: see text]. Then, we determine the exact values of edge-weighted domination numbers for some special classes of graphs and for some special edge weights assignments, and further design linear-time algorithms to compute the edge-weighted domination number of a tree, a cycle, respectively. Finally, based on the above algorithms, we design a linear-time algorithm to find an edge-weighted dominating set of a block-cactus graph, a superclass of both block graphs and cacti.