Geodesic
A Combinatorial Decomposition Theory
Canadian journal of mathematics, Tome 32 (1980) no. 3, pp. 734-765

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
Cunningham, William H.; Edmonds, Jack. A Combinatorial Decomposition Theory. Canadian journal of mathematics, Tome 32 (1980) no. 3, pp. 734-765. doi: 10.4153/CJM-1980-057-7
@article{10_4153_CJM_1980_057_7,
     author = {Cunningham, William H. and Edmonds, Jack},
     title = {A {Combinatorial} {Decomposition} {Theory}},
     journal = {Canadian journal of mathematics},
     pages = {734--765},
     year = {1980},
     volume = {32},
     number = {3},
     doi = {10.4153/CJM-1980-057-7},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-057-7/}
}
TY  - JOUR
AU  - Cunningham, William H.
AU  - Edmonds, Jack
TI  - A Combinatorial Decomposition Theory
JO  - Canadian journal of mathematics
PY  - 1980
SP  - 734
EP  - 765
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-057-7/
DO  - 10.4153/CJM-1980-057-7
ID  - 10_4153_CJM_1980_057_7
ER  - 
%0 Journal Article
%A Cunningham, William H.
%A Edmonds, Jack
%T A Combinatorial Decomposition Theory
%J Canadian journal of mathematics
%D 1980
%P 734-765
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1980-057-7/
%R 10.4153/CJM-1980-057-7
%F 10_4153_CJM_1980_057_7

[1] 1. Ashenhurst, R. L., The decomposition of switching functions, in: Proceedings of the international symposium on the theory of switching (Part 1), (Harvard University Press, Cambridge, 1959). Google Scholar

[2] 2. Berge, C., Graphs and hypergraphs (North Holland, Amsterdam, 1973). Google Scholar

[3] 3. Billera, L. J., Clutter decomposition and monotonie Boolean functions, Annals of the New York Academy of Sciences 175, Articl. 1 (1970), 41–48. Google Scholar

[4] 4. Billera, L. J., On the composition and decomposition of clutters, J. Combinatorial Theor. 11 (1971), 234–245. Google Scholar

[5] 5. Birnbaum, Z. W. and Esary, J. D., Modules of coherent binary systems, SIAM J. Applied Math. 13 (1965), 444–462. Google Scholar

[6] 6. Bixby, R. E., Composition and decomposition of matroids and related topics, Thesis, Cornell University (1972). Google Scholar

[7] 7. Bixby, R. E. and Cunningham, W. H., Matroids, graphs, and 3-connectivity, in: Graph theory and related topics (Academic Press, New York, 1979), 91-103. Google Scholar

[8] 8. Brylawski, T. H., A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235–282. Google Scholar

[9] 9. Chvâtal, V., On certain polytopes associated with graphs, J. Combinatorial Theory. 18 (1975), 138–154. Google Scholar

[10] 10. Cunningham, W. H., A combinatorial decomposition theory, Thesis, University of Waterloo (1973). Google Scholar

[11] 11. Edmonds, J., Matroid partition, Math, of the Decision Sciences, A.M.S. Lectures in Applied Math. 11 (1968), 335–346. Google Scholar

[12] 12. Edmonds, J., Matroid intersection, Annals of Discrete Math. 4 (1979), 39–47. Google Scholar

[13] 13. Edmonds, J. and Giles, R., A min-max relation for submodular functions on graphs, Annals of Discrete Math. 1 (1977), 185–204. Google Scholar

[14] 14. Hopcroft, J. E. and Tarjan, R. E., Isomorphism of planar graphs, in: Complexity of computer computations (Plenum Press, New York, 1972). Google Scholar

[15] 15. Hopcroft, J. E. and Tarjan, R. E., Dividing a graph into triconnected components, SIAM J. Computin. 2 (1973), 135–158. Google Scholar

[16] 16. Lehman, A., A solution of the Shannon switching game, SIAM J. Applied Math. 12 (1964), 687–725. Google Scholar

[17] 17. Maclane, S., A structural characterization of planar combinatorial graphs, Duke Math. J. 3 (1937), 460–472. Google Scholar

[18] 18. Minty, G. J., On the axiomatic foundations of the theories of directed linear graphs, electrical networks, and network-programming, J. Math. Mech. 15 (1966), 485–520. Google Scholar

[19] 19. Richardson, W., Connectivity, decomposition and complexity in matroids, Thesis, University of Waterloo (1973). Google Scholar

[20] 20. Shapley, L. S., On committees, in: New methods of thought and procedure (Springer, New York, 1968). Google Scholar

[21] 21. Smith, C. A. B., Patroids, J. Combinatorial Theory. 16 (1974), 64–76. Google Scholar

[22] 22. Trakhtenbrot, B. A., Towards a theory of non-repeating contact schemes (Russian), Trudi MIAN SSSR 51 (1958), 226–269. Google Scholar

[23] 23. Tutte, W. T., Connectivity in graphs (University of Toronto Press, Toronto, 1966). Google Scholar

[24] 24. Tutte, W. T., Connectivity in matroids, Can. J. Math. 18 (1966), 1301–1324. Google Scholar

[25] 25. Walsh, T. R. S., Counting labelled three-connected and homeomorphically irreducible 2-connected graphs, submitted for publication. Google Scholar

[26] 26. Walsh, T. R. S., Counting unlabelled three-connected graphs, submitted for publication. Google Scholar

[27] 27. Welsh, D. J. A., Matroid theory (Academic Press, London, 1976). Google Scholar

[28] 28. Whitney, H., Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362. Google Scholar

Cité par Sources :