2
$\begingroup$

Let $G$ be a simple finite undirected graph. Let $\{V_1,V_2\}$ be a partition of its vertex set; that is, $V_1\cup V_2=V(G)$ and $V_1\cap V_2=\emptyset$. The partition $\{V_1,V_2\}$ is said to be an internal partition if every vertex has at least as many neighbours in its own part than in the other part. The partition $\{V_1,V_2\}$ is said to be an external partition if every vertex has at most as many neighbours in its own part than in the other part.

It is known that $G$ always has an external partition. The situation is more diverse for internal partitions (eg: see [1]). There are many unresolved problems and conjectures on internal partitions even when the input graph is even regular.

Is partitions that are both internal and external studied in the literature?
(that is, a partition $\{V_1,V_2\}$ such that every vertex has the same number of neighbors in its own part as in the other part).

If it matters, I am more interested in even regular graph (esp. 4-regular graphs) and in partition into equal-sized parts (i.e. $|V_1|=|V_2|$).

[1] Ban, Amir; Linial, Nati, Internal partitions of regular graphs, J. Graph Theory 83, No. 1, 5-18 (2016). ZBL1346.05223.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.