The constructive characterization of (κ,ℓ)-edge-connected digraphs
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.