Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Degree constrained orientations in countable graphs. | Degree constrained orientations in countable graphs Attila Bernáth MTA-ELTE Egervary Research Group EGRES Department of Operations Research Eotvos University Pazmany P. s. 1 C H-1117 Budapest Hungary bernath@ Henning Bruhn Mathematisches Seminar Universitat Hamburg Bundesstrafie 55 20146 Hamburg Germany hbruhn@ Submitted Feb 15 2007 Accepted Sep 17 2008 Published Sep 29 2008 Mathematics Subject Classification 05C20 Abstract Degree constrained orientations are orientations of an undirected graph where the in-degree function satisfies given lower and upper bounds. For finite graphs Frank and Gyarfas 1976 gave a necessary and sufficient condition for the existence of such an orientation. We extend their result to countable graphs. 1 Introduction Orientations of finite graphs are well-studied. An early result is the theorem of Robbins 10 on the existence of a strongly connected orientation. This result has been widely generalised by Nash-Williams 8 in 1960 who described orientations satisfying global or symmetric local edge-connectivity requirements. Ford and Fulkerson 4 investigated when a partial orientation can be completed to a di-eulerian one. As a last example let us cite Frank 5 who characterised the graphs that can be oriented in such a way that there are k directed paths between a specified vertex and every other vertex. In contrast not much is known about orientations of infinite graphs. An exception is an old result of Egyed 3 that extends Robbins theorem on strongly connected orientations. We mention also Thomassen 11 who raised some related conjectures. In this paper we will focus on degree constrained orientations in infinite but countable graphs. These are orientations where the in-degree function . the function counting the number of ingoing edges at each vertex satisfies given lower and upper bounds. Degree constrained orientations have a close relationship to Hall s marriage theorem and Supported by the Algorithmic Discrete .
