| Abstrakt: |
An (s, t)-partition of a graph $$G=(V,E)$$ G=(V,E) is a partition of $$V=V_1\cup V_2$$ V=V1∪V2 such that $$\delta (G[V_1])\ge s$$ δ(G[V1])≥s and $$\delta (G[V_2])\ge t$$ δ(G[V2])≥t . It has been conjectured that, for sufficiently large n, every d-regular graph of order nhas a $$(\lceil \frac{d}{2}\rceil , \lceil \frac{d}{2}\rceil )$$ (⌈d2⌉,⌈d2⌉) -partition (called an internal partition). In this paper, we prove that every d-regular graph of order nhas a $$(\lceil \frac{d}{2}\rceil , \lfloor \frac{d}{2}\rfloor )$$ (⌈d2⌉,⌊d2⌋) partition (called a weak internal partition) for $$d\le 9$$ d≤9 and sufficiently large n. |
Full text from SpringerLink