Stable structure on safe set problems in vertex-weighted graphs
Stable structure on safe set problems in vertex-weighted graphs
复制标题
顶点加权图中安全集问题的稳定结构
DOI：
10.1016/j.ejc.2020.103211
复制
发表时间：
2021
影响因子：
1
通讯作者：
Sakuma Tadashi
中科院分区：
文献类型：
--
作者：
Fujita Shinya;Park Boram;Sakuma Tadashi
Let G be a graph, and let w be a positive real-valued weight function on V (G). For every subset S of V (G), let w (S)=∑ v∈ S w (v). A non-empty subset S⊂ V (G) is a weighted safe set of (G, w) if, for every component C of the subgraph induced by S and every component D of G− S, we have w (C)≥ w (D) whenever there is an edge between C and D. If the subgraph of G induced by a weighted safe set S is connected, then the set S is called a connected weighted safe set of (G, w). The weighted safe number s (G, w) and connected weighted safe number cs (G, w) of (G, w) are the minimum weights w (S) among all weighted safe sets and all connected weighted safe sets of (G, w), respectively. Note that for every pair (G, w), s (G, w)≤ cs (G, w) by their definitions. In [Fujita et al.“On weighted safe set problem on paths and cycles” J. Comb. Optim. 37 (2019) 685–701], it was asked which pair (G, w) satisfies the equality and shown that every weighted cycle satisfies the equality. In this paper, we give a complete list of connected bipartite graphs G such that s (G, w)= cs (G, w) for every weight function w on V (G).
