×

zbMATH — the first resource for mathematics

Orientations of infinite graphs with prescribed edge-connectivity. (English) Zbl 1399.05139
Summary: We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every \(4k\)-edge-connected graph \(G\) contains an immersion of some finite \(2k\)-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that \(G\) need not contain a subdivision of a simple finite graph of large edge-connectivity). Also, every \(8k\)-edge-connected infinite graph has a \(k\)-arc-connected orientation, as conjectured by the author [in: Combinatorial mathematics: Proceedings of the third international conference, held in New York, USA, June 10–14, 1985. New York: New York Academy of Sciences. 402–412 (1989; Zbl 0709.05030)].

MSC:
05C40 Connectivity
05C20 Directed graphs (digraphs), tournaments
05C63 Infinite graphs
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. Aharoni and C. Thomassen: Infinite, highly connected digraphs with no twoarc-disjoint spanning trees, J. Graph Theory 13 (1989), 71–74. · Zbl 0665.05023 · doi:10.1002/jgt.3190130110
[2] J. BarÁt and M. Kriesell: What is on his mind?, Discrete Mathematics 310 (2010), 2573–2583. · Zbl 1208.05003 · doi:10.1016/j.disc.2010.06.007
[3] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications, The MacMillanPress Ltd. (1976).
[4] R. Diestel: Graph Theory, Springer Verlag (1997) and 4th edition (2010).
[5] G. A. Dirac and C. Thomassen: Graphs in which every finite path is contained ina circuit, Math. Ann. 203 (1973), 65–75. · Zbl 0239.05129 · doi:10.1007/BF01349245
[6] J. Edmonds: Minimum partition of a matroid into independent subsets, J. Res. Nat.Bur. Standards Sect. B 69B (1965), 67–72. · Zbl 0192.09101 · doi:10.6028/jres.069B.004
[7] R. Halin: A note on Menger’s theorem for infinite locally finite graphs, Abh. Math.Sem. Univ. Hamburg 40 (1974), 111–114. · Zbl 0277.05121 · doi:10.1007/BF02993589
[8] F. Laviolette: Decompositions of infinite Graphs: I–bond-faithful decompositions, Journal of Combinatorial Theory, Series B 94 (2005), 259–277. · Zbl 1066.05113 · doi:10.1016/j.jctb.2005.01.003
[9] L. LovÁsz: On some connectivity properties of eulerian graphs, Acta Math. Acad.Sci. Hung. 28 (1976), 129–138. · Zbl 0337.05124 · doi:10.1007/BF01902503
[10] W. Mader: A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978), 145–164. · Zbl 0389.05042 · doi:10.1016/S0167-5060(08)70504-1
[11] B. Mohar and C. Thomassen: Graphs on Surfaces, Johns Hopkins University Press(2001). · Zbl 0979.05002
[12] C. St. J. A. Nash-Williams: On orientations, connectivity and odd-vertex-pairingsin finite graphs, Canad. J. Math. 12 (1960), 555–567. · Zbl 0096.38002 · doi:10.4153/CJM-1960-049-6
[13] C. St. J. A. Nash-Williams: Edge-disjoint spanning trees of finite graphs, J. Lon-don Math. Soc. 36 (1961), 445–450. · Zbl 0102.38805
[14] C. St. J. A. Nash-Williams: Infinite graphs-a survey, J. Combin. Theory 3 (1967),286–301. · Zbl 0153.25801 · doi:10.1016/S0021-9800(67)80077-2
[15] C. St. J. A. Nash-Williams: Unexplored and semi-explored territories in graphtheory, in: New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf.,Univ. Michigan, Ann Arbor, MI, 1971), Academic Press, New York (1973), 149–186.
[16] H. E. Robbins: Questions, discussions, and notes: a theorem on graphs, with anapplication to a problem of traffic control, Amer. Math. Monthly 46 (1939), 281–283. · Zbl 0021.35703 · doi:10.2307/2303897
[17] C. Thomassen: 2-Linked Graphs, Europ. J. Combinatorics 1 (1980), 371–378. · Zbl 0457.05044 · doi:10.1016/S0195-6698(80)80039-4
[18] C. Thomassen: Infinite graphs, in: Further Selected Topics in Graph Theory (L.W. Beineke and R.J. Wilson, eds.), Academic Press, London (1983), 129–160.
[19] C. Thomassen: Configurations in graphs of large minimum degree, connectivity, orchromatic number, in: Combinatorial Mathematics: Proceedings of the Third Interna-tional Conference, New York 1985, Ann. New York Acad. Sci., New York 555 (1989), 402–412.
[20] C. Thomassen: The weak 3-ow conjecture and the weak circular ow conjecture,J. Combin. Theory Ser. B. 102 (2012), 521–529. · Zbl 1239.05083 · doi:10.1016/j.jctb.2011.09.003
[21] W. T. Tutte: On the problem of decomposing a graph into n connected factors, J.London Math. Soc. 36 (1961), 221–230. · Zbl 0096.38001 · doi:10.1112/jlms/s1-36.1.221
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.