Balanced graphs with minimum degree constraints
Let \(G\) be a graph of order \(n\) with minimum vertex degree \(\delta(G)\) or shortly \(\delta\), \(n\equiv\delta\pmod 2\). If \(X\subseteq V(G)\) then \(\langle X\rangle\) is the induced subgraph of \(G\) with vertex set \(X\). Suppose that \(0\leq\delta\leq n-2\), \(0\leq i\leq\left\lfloor{1\over 2}\delta\right\rfloor\). By an \((i,\delta)\)-partition of \(G\) the author means a partition \((X,Y)\) of \(V(G)\) with (i) \(| X|=\left\lceil{1\over 2}n\right\rceil+i\), \(| Y|=\left\lfloor{1\over 2}n\right\rfloor-i\), and (ii) \(\delta(\langle X\rangle)\geq\left\lceil{1\over 2}\delta\right\rceil+i\), \(\delta(\langle Y\rangle)\geq\left\lfloor{1\over 2}\delta\right\rfloor-i\). It is shown that if \(G\) is connected then \(G\) possesses an \((i,\delta)\)-partition for some \(i, 0\leq i\leq\left\lfloor{1\over 2}\delta\right\rfloor-1\). The context of the paper under review was discussed in the author's earlier paper [Discrete Math. 68, No. 2/3, 299-307 (1988; Zbl 0644.05030)].
scientific article; zbMATH DE number 64639