Premium
On partitioning the edges of graphs into connected subgraphs
Author(s) -
Jünger M.,
Reinelt G.,
Pulleyblank W. R.
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090416
Subject(s) - partition (number theory) , combinatorics , mathematics , existential quantification , frequency partition of a graph , graph partition , graph , discrete mathematics , graph power , line graph
For any positive integer s , an s ‐partition of a graph G = ( V , E ) is a partition of E into E 1 ∪ E 2 ∪… ∪ E k , where ∣ E i ∣ = s for 1 ≤ i ≤ k − 1 and 1 ≤ ∣ E k ∣ ≤ s and each E i 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 .