عدد تحميلي صفر چه گراف هايي با ساختار مايسيليسكي با ماكسيمم پوچي آنها برابر است؟

The zero forcing number of Which Mycielski construction graphs are equal to their maximum nullity?

فرض كنيد S نشان دهنده مجموعه رئوس با رنگ سياه (اوليه) گراف G باشد. قانون تغيير رنگ، رنگ يك رأس سفيد را به سياه تبديل مي كند اگر رأس سفيد u تنها همسايه سفيد رأس سياه v باشد. مجموعه S يك مجموعه تحميلي صفر G است هرگاه بعد از تعداد متناهي اعمال قانون تغيير رنگ، رنگ تمامي رئوس به سياه تغيير كنند. تعداد اعضاي يك مجموعه‌ي تحميلي صفر با كمترين عضو را عدد تحميلي صفر گراف مي نامند. در اين مقاله عدد تحميلي صفر و ماكسيمم پوچي برخي گراف‌ها با ساختار مايسيليسكي را بررسي مي‌كنيم. به ويژه به ازاي برخي گراف‌ها با اين ساختار نشان مي‌دهيم عدد تحميلي صفر گراف با ماكسيمم پوچي آن برابر است. همچنين عدد تحميلي صفر و ماكسيمم پوچي گراف‌ها‌ي مايسيليسكي μ(Kn)، μ(Cn)و گراف‌هاي همبند با حداقل 4 رأس را محاسبه كرده‌ايم.

Let S denote the (initial) set of black vertices of graph G. The color-change rule converts the color of a vertex from white to black if the white vertex u is the only white neighbor of a black vertex v. The set S is said to be a zero forcing set of G if all vertices of G will be turned black after finitely many applications of the color-change rule. The zero forcing number of G is the minimum of |S| over all zero forcing sets S ⊆ V (G). In this paper, we study the zero forcing number and maximum nullity of Mycielski’s construction in some graphs. In particular, we show that the zero forcing number of some graphs with this construction equals to maximum nullity. Also we calculate the zero forcing number and maximum nullity of Mycielski graphs μ(K_n)، μ(C_n) and connected graphs of order at least 4.