کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9512468 | 1632466 | 2005 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
α-Extendable paths in infinite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
An α-extendable path of a graph G is defined inductively as follows: every path is 0-extendable; a path is (α+1)-extendable if, for every finite SâV(G), it has an α-extendable extension which covers S; a path is α-extendable for a limit ordinal α if it is β-extendable for every ordinal β<α. Finally a path is â-extendable if it is α-extendable for every ordinal α. If a graph has an â-extendable path, then every countable set of its vertices is coverable by a (finite or infinite) path; in particular, if such a graph is countable then it has a Hamiltonian infinite path. We show that, for every graph G, there exists an ordinal α<|G|+ such that every α-extendable path of G is â-extendable. The smallest of these ordinals is called the path-extendability rank of G. In this paper we study some properties of this ordinal. In particular we prove that the graphs for which almost all vertices have infinite degrees, and those whose thickness is finite and for which almost all vertices have finite degree, have a finite path-extendability rank. This gives partial answers to a problem of Nash-Williams (Proceedings of the Second Chapel Hill Conference on Combinatorial Mathematics and its Applications, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1970, p. 547).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 291, Issues 1â3, 6 March 2005, Pages 175-189
Journal: Discrete Mathematics - Volume 291, Issues 1â3, 6 March 2005, Pages 175-189
نویسندگان
Norbert Polat,