Graph decomposition with constraints in the minimum degree (Q1102305)

In the paper are investigated decompositions of finite simple graph G with minimum degree \(\delta\) (G)\(\geq \delta (n\equiv \delta (mod 2))\) n denotes the cardinality of V(G). Let max(k,G) denote the set of all k- subsets \(A\subseteq V(G)\) such that the number of edges in the induced subgraph \(<A>\) is a maximum. All subsets of max(k,G) are called dense sets. It is proved that for some \(i\in \{0,1,...,1/2\}\) there exists a partition (X,Y) of V(G) such that (i) \(| X| =\lceil (1/2)n\rceil +i\), \(| Y| =\lfloor n/2\rfloor -i,\) (ii) \(\delta (X)\geq \lceil \delta /2\rceil +i\), \(\delta\) (Y)\(\geq \lfloor \delta /2\rfloor -i,\) (iii) X or Y is dense in G. Two subsets of V(G) form a weak (i,\(\delta)\) partition if condition (i) and (ii) are fulfilled. There are formulated some conjectures concerning weak decomposability of graphs.