On the weighted safe set problem on paths and cycles

Shinya Fujita (), Tommy Jensen (), Boram Park () and Tadashi Sakuma ()
Additional contact information
Shinya Fujita: Yokohama City University
Tommy Jensen: Aarhus Universitet
Boram Park: Ajou University
Tadashi Sakuma: Yamagata University

Journal of Combinatorial Optimization, 2019, vol. 37, issue 2, No 16, 685-701

Abstract: Abstract 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)=\sum _{v \in X} w(v)$$ w ( X ) = ∑ v ∈ X w ( v ) . A non-empty subset $$S \subset V(G)$$ 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$$ G - S , we have $$w(C) \ge w(D)$$ 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 $$\mathrm{s}(G,w)$$ s ( G , w ) and connected weighted safe number $$\mathrm{cs}(G,w)$$ 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. It is easy to see that for any pair (G, w), $$\mathrm{s}(G,w) \le \mathrm{cs}(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.

Keywords: Safe set; Connected safe set; Weighted graph; Safe-finite; Subgraph component polynomial (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0316-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:2:d:10.1007_s10878-018-0316-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0316-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().