Let be a graph and let be a positive weight function on the vertices of G. For every subset X of V, let . A non‐empty subset is a weighted safe set if, for every component C of the subgraph induced by S and every component D of , we have whenever there is an edge between C and D. If the subgraph induced by a weighted safe set S is connected, then the set S is called a weighted connected safe set. In this article, we show that the problem of computing the minimum weight of a safe set is ‐hard for trees, even if the underlying tree is restricted to be a star, but it is polynomially solvable for paths. We also give an time 2‐approximation algorithm for finding a weighted connected safe set with minimum weight in a weighted tree. Then, as a generalization of the concept of a minimum safe set, we define the concept of a parameterized infinite family of proper central subgraphs on weighted trees, whose polar ends are the vertex set of the tree and the centroid points. We show that each of these central subgraphs includes a centroid point.

We consider a forbidden rainbow structure condition which implies that an edge colored complete graph has an almost spanning monochromatic subgraph with high connectivity. Namely, we classify the connected graphs $G$ that satisfy the following statement: If $n\,{\gg}\,m\,{\gg}\,k$ are integers, then any rainbow $G$-free coloring of the edges of $K_{n}$ using $m$ colors contains a monochromatic $k$-connected subgraph of order at least $n - f(G, k, m)$, where $f$ does not depend on $n$.

The balanced decomposition number $f(G)$ of a graph G was introduced by Fujita and Nakamigawa [Discr. Appl. Math., 156 (2008), pp. 3339–3344]. A balanced coloring of a graph G is a coloring of some of the vertices of G with two colors, such that there is the same number of vertices in each color. Then, $f(G)$ is the minimum integer s with the following property: For any balanced coloring of G, there is a partition $V(G)=V_1\,\dot\cup\,\cdots\,\dot\cup\,V_r$ such that, for every i, $V_i$ induces a connected subgraph, $|V_i|\leq s$, and $V_i$ contains the same number of colored vertices in each color. Fujita and Nakamigawa studied the function $f(G)$ for many basic families of graphs, and demonstrated some applications. In this paper, we shall continue the study of the function $f(G)$. We give a characterization for noncomplete graphs G of order n which are $\lfloor\frac{n}{2}\rfloor$-connected, in view of the balanced decomposition number. We shall prove that a necessary and sufficient condition for such $\lfloor\frac{n}{2}\rfloor$-connected graphs G is $f(G)=3$. We shall also determine $f(G)$ when G is a complete multipartite graph, and when G is a generalized $\Theta$-graph (i.e., a graph which is a subdivision of a multiple edge). Some applications will also be discussed. Further results about the balanced decomposition number also appear in two subsequent papers by Fujita and Liu.