On packing connectors

J.C.M. Keijsper; A. Schrijver

doi:10.1006/jctb.1998.1825

On packing connectors

J.C.M. Keijsper, A. Schrijver

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

2 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	184-188
Aantal pagina's	5
Tijdschrift	Journal of Combinatorial Theory, Series B
Volume	73
Nummer van het tijdschrift	2
DOI's	https://doi.org/10.1006/jctb.1998.1825
Status	Gepubliceerd - 1998

Toegang tot document

10.1006/jctb.1998.1825

Citeer dit

@article{92c9c810103a49508fb6486131a887d3,

title = "On packing connectors",

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{\"o}nig on disjoint edge covers in a bipartite graph.",

author = "J.C.M. Keijsper and A. Schrijver",

year = "1998",

doi = "10.1006/jctb.1998.1825",

language = "English",

volume = "73",

pages = "184--188",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - On packing connectors

AU - Keijsper, J.C.M.

AU - Schrijver, A.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

U2 - 10.1006/jctb.1998.1825

DO - 10.1006/jctb.1998.1825

M3 - Article

SN - 0095-8956

VL - 73

SP - 184

EP - 188

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

On packing connectors

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit