The constructive characterization of (κ,ℓ)-edge-connected digraphs

Combinatorica - Tập 31 - Trang 201-223 - 2011
Erika R. Kovács1, László A. Végh1
1Department of Operations Research, Eötvös University MTA-ELTE Egerváry Research Group (EGRES), Budapest, Hungary

Tóm tắt

We give a constructive characterization for (κ, ℓ)-edge-connected digraphs, proving a conjecture of Frank.

Tài liệu tham khảo

J. Edmonds: Edge disjoint branchings, in: Combinatorial Algorithms (B. Rustin, ed.), pages 91–96, Academic Press, New York, 1973. A. Frank: On the orientation of graphs, J. Comb. Theory, Ser. B. 28(3) (1980), 251–261. A. Frank: Connectivity augmentation problems in network design, in: Mathematical Programming: State of the Art ( J. Birge and K. Murty, eds.), pages 34–63, The University of Michigan, 1999. A. Frank: Edge-connection of graphs, digraphs, and hypergraphs; in: More sets, graphs and numbers ( E. Győri, G. Katona, and L. Lovász, eds.), Bolyai Mathematical Society Math. Studies, volume 5, pages 93–142, Springer Verlag, 2006. A. Frank and Z. Király: Graph orientations with edge-connection and parity constraints, Combinatorica 22(1) (2002), 47–70. A. Frank and L. Szegő: Constructive characterizations for packing and covering with trees, Discrete Appl. Math. 131(2) (2003), 347–371. T. Király: The splitting off operation and its applications, Master’s thesis, Eötvös University, Budapest, 1999, available online at http://www.cs.elte.hu. E. R. Kovács and L. A. Végh: Constructive characterization theorems in combinatorial optimization, RIMS Kôkyûroku Bessatsu 23 (2010), 147–169. W. Mader: Konstruktion aller n-fach kantenzusammenhängenden Digraphen, Europ. J. Combinatorics 3 (1982), 63–67. W. T. Tutte: On the problem of decomposing a graph into n connected factors, J. London Math. Soc. s1–36 (1961), 221–230.