TY - JOUR
T1 - On the weighted safe set problem on paths and cycles
AU - Fujita, Shinya
AU - Jensen, Tommy
AU - Park, Boram
AU - Sakuma, Tadashi
PY - 2019/2
Y1 - 2019/2
N2 -
Let G be a graph, and let w be a positive real-valued weight function on V(G). For every subset X of V(G), let w(X) = ∑
v
∈
X
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 numbers (G, w) and connected weighted safe numbercs (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. It is easy to see that for any pair (G, w), s (G, w) ≤ cs (G, w) by their definitions. In this paper, we discuss the possible equality when G is a path or a cycle. We also give an answer to a problem due to Tittmann et al. (Eur J Combin 32:954–974, 2011) concerning subgraph component polynomials for cycles and complete graphs.
AB -
Let G be a graph, and let w be a positive real-valued weight function on V(G). For every subset X of V(G), let w(X) = ∑
v
∈
X
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 numbers (G, w) and connected weighted safe numbercs (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. It is easy to see that for any pair (G, w), s (G, w) ≤ cs (G, w) by their definitions. In this paper, we discuss the possible equality when G is a path or a cycle. We also give an answer to a problem due to Tittmann et al. (Eur J Combin 32:954–974, 2011) concerning subgraph component polynomials for cycles and complete graphs.
KW - Connected safe set
KW - Safe set
KW - Safe-finite
KW - Subgraph component polynomial
KW - Weighted graph
UR - https://www.scopus.com/pages/publications/85048039992
U2 - 10.1007/s10878-018-0316-4
DO - 10.1007/s10878-018-0316-4
M3 - Journal article
AN - SCOPUS:85048039992
SN - 1382-6905
VL - 37
SP - 685
EP - 701
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 2
ER -