Balanced graphs with minimum degree constraints (Q1193451): Difference between revisions

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)].