Weak Internal Partition of Regular Graphs

Abstract

An (s, t)-partition of a graph $G=(V,E)$ is a partition of $V=V_1\cup V_2$ such that $\delta (G[V_1])\ge s$ and $\delta (G[V_2])\ge t$. It has been conjectured that, for sufficiently large n, every d-regular graph of order n has a $(\lceil \frac{d}{2}\rceil , \lceil \frac{d}{2}\rceil )$-partition (called an internal partition). In this paper, we prove that every d-regular graph of order n has a $(\lceil \frac{d}{2}\rceil , \lfloor \frac{d}{2}\rfloor )$ partition (called a weak internal partition) for $d\le 9$ and sufficiently large n.

Keywords

Internal partition / External partition / Regular graph

Funding

NNSF(11671376)