Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T11:59:19.041Z Has data issue: false hasContentIssue false

A Combinatorial Decomposition Theory

Published online by Cambridge University Press:  20 November 2018

William H. Cunningham
Affiliation:
Carleton University, Ottaway Ontario
Jack Edmonds
Affiliation:
University of Waterloo, Waterloo, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Given a finite undirected graph G and A ⊆ E(G), G(A) denotes the subgraph of G having edge-set A and having no isolated vertices. For a partition {E1, E2} of E(G), W(G; E1) denotes the set V(G(E1)) ⋂ V(G(E 2)). We say that Gis non-separable if it is connected and for every proper, non-empty subset A of E(G), we have |W(G; A)| ≧ 2. A split of a non-separable graph Gis a partition {E1, E2 } of E(G) such that

|E1 | ≧ 2 ≧ |E2| and |W(G; E1)| = 2.

Where {E1, E2 }is a split of G, W(G; E2) = {u, v}, and e is an element not in E(G), we form graphs Gi i= 1 and 2, by adding e to G(Ei) as an edge joining u to v.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1980