A Combinatorial Decomposition Theory

Abstract

Given a finite undirected graphGandA⊆E(G),G(A)denotes the subgraph ofGhaving edge-setAand having no isolated vertices. For a partition {E₁, E₂}ofE(G),W(G; E₁)denotes the setV(G(E₁))⋂V(G(E₂)). We say thatGisnon-separableif it is connected and for every proper, non-empty subsetAofE(G), we have |W(G;A)| ≧ 2. Asplitof a non-separable graphGis a partition {E₁, E₂} ofE(G)such that|E₁| ≧ 2 ≧ |E₂| and |W(G; E₁)| = 2.Where {E₁, E₂} is a split ofG, W(G; E₂)= {u, v}, andeis an element not inE(G),we form graphsG_ii= 1 and 2, by addingetoG(E_i)as an edge joiningutov.