On packing connectors

J.C.M. Keijsper, A. Schrijver

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)

    Abstract

    Given an undirected graphG=(V, E) and a partition {S, T} ofV, anS-Tconnector is a set of edgesF¿Esuch that every component of the subgraph (V, F) intersects bothSandT. We show thatGhaskedge-disjointS-Tconnectors if and only if |dG(V1)¿…¿dG(Vt)|¿ktfor every collection {V1, …, Vt} of disjoint nonempty subsets ofSand for every such collection of subsets ofT. This is a common generalization of a theorem of Tutte and Nash-Williams on disjoint spanning trees and a theorem of König on disjoint edge covers in a bipartite graph.
    Original languageEnglish
    Pages (from-to)184-188
    Number of pages5
    JournalJournal of Combinatorial Theory, Series B
    Volume73
    Issue number2
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'On packing connectors'. Together they form a unique fingerprint.

  • Cite this