Edge–weighted domination in graphs
Yancai Zhao
Source record
Source: Crossref
Published: Oct 27, 2025
DOI: 10.1142/s1793830925501447
Open original source ↗Source abstract
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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.