کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4600098 | 1336836 | 2013 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two-lit trees for lit-only σ-game
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A configuration of the lit-only σ-game on a finite graph Γ is an assignment of one of two states, on or off, to all vertices of Γ. Given a configuration, a move of the lit-only σ-game on Γ allows the player to choose an on vertex s of Γ and change the states of all neighbors of s. Given any integer k, we say that Γ is k-lit if, for any configuration, the number of on vertices can be reduced to at most k by a finite sequence of moves. Assume that Γ is a tree with a perfect matching. We show that Γ is 1-lit and any tree obtained from Γ by adding a new vertex on an edge of Γ is 2-lit.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 438, Issue 3, 1 February 2013, Pages 1057-1066
Journal: Linear Algebra and its Applications - Volume 438, Issue 3, 1 February 2013, Pages 1057-1066