کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649813 | 1342467 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quasi-kernels and quasi-sinks in infinite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a directed graph G=(V,E)G=(V,E) an independent set A⊂VA⊂V is called quasi-kernel (quasi-sink) iff for each point vv there is a path of length at most 2 from some point of AA to vv (from vv to some point of AA). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We study the following conjecture: for any digraph G=(V,E)G=(V,E) there is a a partition (V0,V1)(V0,V1) of the vertex set such that the induced subgraph G[V0]G[V0] has a quasi-kernel and the induced subgraph G[V1]G[V1] has a quasi-sink.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3040–3048
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3040–3048
نویسندگان
Péter L. Erdős, Lajos Soukup,