Abstract: | For any positive integer s, an s-partition of a graph G = (V, E) is a partition of E into E1 ∪ E2 ∪…? ∪ Ek, where ∣Ei∣ = s for 1 ≤ i ≤ k ? 1 and 1 ≤ ∣Ek∣ ≤ s and each Ei induces a connected subgraph of G. We prove - (i) If G is connected, then there exists a 2-partition, but not necessarily a 3-partition;
- (ii) If G is 2-edge connected, then there exists a 3-partition, but not necessarily a 4-partition;
- (iii) If G is 3-edge connected, then there exists a 4-partition;
- (iv) If G is 4-edge connected, then there exists an s-partition for all s.
|