Aarhus University Seal / Aarhus Universitets segl

On the weighted safe set problem on paths and cycles

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Shinya Fujita, Yokohama City University
  • ,
  • Tommy Jensen
  • ,
  • Boram Park, Ajou University
  • ,
  • Tadashi Sakuma, Yamagata University

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.

Original languageEnglish
JournalJournal of Combinatorial Optimization
Pages (from-to)685-701
Number of pages17
Publication statusPublished - Feb 2019

    Research areas

  • Connected safe set, Safe set, Safe-finite, Subgraph component polynomial, Weighted graph

See relations at Aarhus University Citationformats

ID: 161349317