Graphical decompositions (Q1322291)

Suppose the vertices of the \(k\)-regular connected graph \(G_ n\) can be partitioned into two sets \(X\) and \(Y\) such that all vertex-degrees in the subgraphs induced by \(X\) and \(Y\) are at least \(\lceil k/2 \rceil\) and \(\lfloor k/2 \rfloor\), respectively. Let \(W_ k(G_ n)\) denote the minimum value of \(\| X |-| Y \|\) over all such partitions of the vertices of \(G_ n\) and let \(W_ k (n)\) denote the maximum value of \(W_ k (G_ n)\) over all such graphs \(G_ n\). The author obtains the value of or upper bounds for \(W_ k (n)\) for \(1 \leq k \leq 7\) and \(n\) sufficiently large, among other things. For example, he shows that \(W_ 7(n) \leq (17n + 356)/33\) if \(n \geq 24\) and \(n\) is even.