کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646847 | 1342315 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Point determining digraphs, {0,1}{0,1}-matrix partitions, and dualities in full homomorphisms
ترجمه فارسی عنوان
ارقام تعریف نقطه، {0.1} {0،1} پارتیشنهای ماتریس و دوگانگی در همگن سازان کامل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پارتیشن ماتریس، رنگ آمیزی متمرکز همامورفیسم کامل نقاط تعریف نقطه، مجموعه ی همگن، حداقل انسداد
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A digraph DD is point determining if for any two distinct vertices u,vu,v there exists a vertex ww which has an arc to (or from) exactly one of u,vu,v. We prove that every point-determining digraph DD contains a vertex vv such that D−vD−v is also point determining. We apply this result to show that for any {0,1}{0,1}-matrix MM, with kk diagonal zeros and ℓℓ diagonal ones, the size of a minimal MM-obstruction is at most (k+1)(ℓ+1)(k+1)(ℓ+1). This is a best possible bound, and it extends the results of Sumner, and of Feder and Hell, from undirected graphs and symmetric matrices to digraphs and general matrices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 10, 6 October 2015, Pages 1755–1762
Journal: Discrete Mathematics - Volume 338, Issue 10, 6 October 2015, Pages 1755–1762
نویسندگان
Pavol Hell, César Hernández-Cruz,