Partition of graphs with maximum degree ratio (Q6945271)

The authors in this work are concerned with the important problem of partitioning the vertex set of a graph subject to certain constraints. Their problem is related to the degree ratio. First, the authors define what they mean by the satisfaction number of a vertex $v$ in $V_i$. This parameter is defined as the ratio of the size of the closed neighborhood of a vertex $v$ in one of the two partitions $V_1$ and $V_2$, say $v$ is in $V_i$ to the size of the closed neighborhood of $v$ in the whole of $G$. The degree ratio is then defined as the ratio of the largest worst ratio over all nontrivial partitions. The worst ratio over all the vertices then reveals the quality of the partition. In this article, the authors compute this degree ratio parameter for certain classes of graphs. They also derive certain NP completeness results for the family of regular graphs.