مریم عطاپور

فرض کنید G=(V,E) گرافی با مجموعه رئوسV و مجموعه یالهای E باشد. مجموعه S⊆V را یک مجموعه احاطه گر در G نامند هرگاه هر رأس از V-S با حداقل یک رأس از S مجاور باشد. مجموعه احاطه گر S_0 از گراف G را یک مجموعه 1- امن دایم گویند هرگاه به ازای هر عدد صحیح مثبت k و هر دنبالهv_1,…,v_k از رئوس، دنباله ای مانند u_1,…,u_k با شرط u_i∈S_(i-1) موجود باشد که u_i=v_i یا u_i v_i∈E و S_i=(S_(i-1)-{u_i })∪{v_i } یک مجموعه احاطه گر باشد. اگر روی هریک از رئوس یک مجموعه 1- امن دایم در G یک محافظ قرار دهیم، آنگاه به ازای هر دنباله از حملات به رئوس، با حرکت یک محافظ در امتداد یکی از یالهای مجاور آن، مجموعه حاصل، باز هم امن باقی می ماند. اگر به ازای هر دنباله از حملات به رئوس G، تمام محافظان بتوانند در امتداد یکی از یالهای مجاور حرکت کنند و مجموعه حاصل باز هم امن بماند، آنگاه این مجموعه را یک مجموعه -m امن دایم نامند. کمترین تعداد اعضای یک مجموعه -m امن دایم را عدد -m امن دایم G نامیده و با σ_m (G) نشان می دهند. زیرتقسیم یال e=uv از G عبارت است از حذف e و افزودن رأس جدید w و یالهای uw و wv. عدد زیرتقسیم -m امن دایم G، 〖sd〗_(σ_m ) (G)، عبارت است از کمترین تعداد یالهایی از G که با زیرتقسیم آنها عدد -m امن دایم گراف افزایش می یابد. در این مقاله نشان می دهیم که عدد زیرتقسیم -m امن دایم در هر گراف حداکثر 3 است.